I have been looking at the problems on Project Euler and a number of them have required me to be able to find the prime factorisation of a given number.
While looking for quick ways to do this, I came across a website that could perform this calculation and had it's source code available too.
The crux of the algorithm was this method: (I hope java code on this site is OK)
public static long smallestPrimeFactor( final long n ) {
if (n==0 || n==1) return n;
if (n%2==0) return 2;
if (n%3==0) return 3;
if (n%5==0) return 5;
for (int i = 7; (i*i) <= n; i += 30 ) {
if ( n % i == 0 ) {
return i;
}
if ( n % ( i+4 ) == 0) {
return i+4;
}
if ( n % ( i+6 ) == 0) {
return i+6;
}
if ( n % ( i+10 ) == 0) {
return i+10;
}
if ( n % ( i+12 ) == 0) {
return i+12;
}
if ( n % ( i+16 ) == 0) {
return i+16;
}
if ( n % ( i+22 ) == 0) {
return i+22;
}
if ( n % ( i+24 ) == 0) {
return i+24;
}
}
return n;
}
The part that really fascinates me is the loop that starts at 7, then considers some gaps and then increments by 30 before carrying on. This is the list of the first few numbers from the sequence:
7, 11, 13, 17, 19, 23, 29, 31,
37, 41, 43, 47, 49, 53, 59, 61,
67, 71, 73, 77, 79, 83, 89, 91,
97, 101, 103, 107, 109, 113, 119, 121,
127, 131, 133, 137, 139, 143, 149, 151,
157, 161, 163, 167, 169, 173, 179, 181,
187, 191, 193, 197, 199, 203, 209, 211
Obviously this loop generates some numbers that are not prime numbers (49, 77, 91 for example) but it does appear to produce every possible prime number less than the square root of the given number.
Am I correct in believing that this loop will produce every prime number? And if so, is there a proof or some mathematical reasoning behind why that is the case?