Thread: greatest common divisor is a prime number (pairs of numbers problem in C)

Originally Posted by flp1969

This is essentially the same routine I posted before, except you check for divisors by 3 in the beginning (starting the checks in the loop, for divisors by 5)...

No, it is not the same: your routine makes use of the fact that all primes greater than 2 are of the form 2k+1; this routine makes use of the fact that all primes greater than 3 are of the forms 6k-1 or 6k+1. On average, this routine makes two-thirds as many checks for divisibility.

Originally Posted by flp1969

A better way, which can consume a lot of memory, is to check for the previously found primes less or equal to the square rooot of n...

That's what I wrote in post #25. I think it was the approach I took some years (over a decade?) back when someone posted some primality testing challenge here, but my solution wasn't very good compared with some others as it wasn't tailored to the challenge.

Originally Posted by flp1969

I see... but nobody, until now, proved if this is correct... I have my doubts...

Refer to my post #20 at the end. I've demonstrated that it is mathematically correct.

To make it easier:

Originally Posted by laserlight

We could observe that any integer >= 6 could be expressed in the form 6k+0, 6k+1, 6k+2, 6k+3, 6k+4, or 6k+5, for some integer k > 0. Clearly, 6k+0, 6k+2, and 6k+4 are divisible by 2, and hence cannot be prime. 6k+3 is divisible by 3, and hence cannot be prime. Therefore, only those of the form 6k+1 and 6k+5 could be prime, i.e., if an integer >= 6 is prime, it must be of one of these two forms. But 6k+5 is congruent to 6k-1 under modulo 6, hence the statement expresses this as 6k+-1. Furthermore, 5 is also prime yet is in the form 6k-1, hence the range was specified as being > 3 rather than >= 6.

Originally Posted by Hodor

Well, I don't know where there is a formal proof but it's mentioned on the Wikipedia page (Primality test - Wikipedia)

Here's an interesting result. Another way to state the 6x +- 1 identity: the square of any prime (> 3) minus one is always a multiple of 24.

Originally Posted by laserlight

flp1969: following your example from post #16, we're probably looking at something along these lines:

Code:

int isPrime(unsigned int n)
{
    if (n < 2)
        return 0;
    if (n <= 3)
        return 1;
    if (n % 2 == 0 || n % 3 == 0)
        return 0;

    unsigned int sqrt_ = (unsigned int)sqrt(n);

    // We only need to check divisors of the forms 6k-1 and 6k+1, for k > 0
    for (unsigned int i = 5; i <= sqrt_; i += 4) // +4 because +2 in the loop body
    {
        if (n % i == 0)
            return 0;
        i += 2
        if (n % i == 0)
            return 0;
    }
    return 1;
}

I guess it's also possible to construct this more carefully with a check for the square root after each modulo test, but the idea remains the same: we're skipping numbers with an alternating +4 instead of always doing +2 (or +1) because we know that the possible prime factors to test with are of those two forms.

Impressive! Much more efficient than the standard approach. I also like the fact that you chose to test mod 2 and 3 rather than 6. Way less cryptic.

Code:

    // We only need to check divisors of the forms 6k-1 and 6k+1, for k > 0
    for (unsigned int i = 5; i <= sqrt_; i += 4) // +4 because +2 in the loop body
    {
        if (n % i == 0)
            return 0;
        i += 2
        if (n % i == 0)
            return 0;
    }

Should not the for loop be like below?

Code:

    // We only need to check divisors of the forms 6k-1 and 6k+1, for k > 0
    for (unsigned int i = 6; (i-1) <= sqrt_; i += 6)
    {
        if (n % (i-1) == 0)
            return 0;
        if (n % (i+1) == 0)
            return 0;
    }

Originally Posted by stahta01

Should not the for loop be like below?

You could do that, but it could end up with three additions or subtractions (4, but 1 is repeated) per iteration instead of two.