[Math] Smallest Prime Factor – Why does this algorithm find prime numbers

prime factorizationprime numbers

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?

Best Answer

In the loop $i$ is equal to $30k+7$, where $k$ is a non-negative integer. Let's consider what values can't be prime. I'll list the offsets and remove them as they're eliminated. $$0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29$$

We start with $7$, which is odd. Adding another odd number would give us an even number, which is divisible by $2$. Eliminate those. $$0,2,4,6,8,10,12,14,16,18,20,22,24,26,28$$

We're adding multiples of $30$, which are divisible by $3$. The last digit is $7$. Adding $2$ would make it $9$, making the whole number divisible by $3$. So $2$ gets skipped, so well as $2+3k$. Eliminate those. $$0,4,6,10,12,16,18,22,24,28$$

Same logic for $5$. Since the last digit is $7$ without an offset, then adding $3,8,13$, etc, would make it a multiple of $5$. Eliminate those. $$0,4,6,10,12,16,22,24$$

And you're left with the numbers that are checked. We increment by $30$ since $2\cdot3\cdot5=30$, and we checked those at the very beginning. Adding $30$ produces the same pattern of divisibility by those numbers at the same offsets. So from then on we just need to dodge those offsets.

Related Question