Smallest Prime Factor - Why does this algorithm find prime numbers?

Question

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?

Answer 1

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.

Answer 2

This should produce all primes. First, $i=30j+7$ for some $j$. Now with this in mind, take a look at the values that get skipped. Obviously, first thing, it skips all even numbers. As an example though, look at the first odd number it skips, $i+2=30j+9=3(10j+3)$. You will find that all the numbers skipped are similarly multiples of $3$ or $5$. In other words, everything it skips is composite.

Answer 3

The code you posted in fact is not very efficient. The way it works is this:

The purpose is ro return the smallest prime factor of number n.

At first it does checks for trivial/simple cases (whether n is divisable by 2,3,5, the first 3 prime numbers)

Then the loop starts fromt the next prime number (=7) and checks up to sqrt(n) (which is enough, but not the most efficient check for factoring n)

The checks inside the loop check for square-free factors and not multiples of 2,3,5 (limited Eratosthenes' sieve) (thus primes)