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

1. 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. 2. Originally Posted by laserlight 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.
I see... but nobody, until now, proved if this is correct... I have my doubts... 3. 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. 4. Originally Posted by flp1969 I see... but nobody, until now, proved if this is correct... I have my doubts...
Well, I don't know where there is a formal proof but it's mentioned on the Wikipedia page (Primality test - Wikipedia)
The algorithm can be improved further by observing that all primes greater than 6 are of the form 6k ± 1. 5. 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.  7. 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. 8. 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;
}``` 9. 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. Popular pages Recent additions int, number, numbers, pairs, prime 