Originally Posted by
Sir Galahad
Minor point: one is not prime!
Another optimization is to use multiplication in place of the sqrt() call. It just tends to run faster. You can also take advantage of the fact that any prime p > 3 is always in the form 6x +- 1. So if n % 6 doesn't equal 1 or 5 then it can't possibly be prime.
Good point... 1 isn't prime as well...
How to use multiplication instead of square root?
I didn't get it the '6x ± 1' tip. If this is true, than criptographic algorithms like RSA would be very easy to break... Do you have any proof?
119 or 121, for example, aren't primes (6*20 ± 1): 17 * 7 = 119 and 11 * 11 = 121.
Even testing for the remainder for 1 and 5 you get a lot of non primes in UINT_MAX/6 range:
Code:
/* prime.c */
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <errno.h>
#include <limits.h>
#include <math.h>
static int isPrime( unsigned int );
int main( void )
{
unsigned int n, m, o;
for (n = 1; n < UINT_MAX/6; n++)
{
int p1, p2;
unsigned int r;
m = 6*n-1;
o = 6*n+1;
r = n % 6;
p1 = isPrime(m);
p2 = isPrime(o);
// Shows all values in form 6x±1 which aren't primes
if ( ! p1 && ! p2 && ( r == 1 || r == 5 ) )
printf( "%u or %u, x=%u (remainder=%u)\n", m, o, n, r );
}
}
int isPrime( unsigned int n )
{
unsigned int sqrt_, i;
// To be mathematically correct, zero AND one aren't primes.
if ( n < 2 )
return 0;
// 2 and 3 are always primes (special cases).
if ( n <= 3 )
return 1;
// if n is even, isn't prime for sure!
if ( !( n & 1 ) )
return 0;
// Calculates the upper limit and must be odd.
sqrt_ = sqrt( n );
if ( !( sqrt_ & 1 ) )
sqrt_--;
// We need to check only odd divisors starting from 3.
for ( i = 3; i <= sqrt_; i += 2 )
{
// if n is divisible by any of them, not a prime!
if ( !( n % i ) )
return 0;
}
// if we get here, it is a prime.
return 1;
}
Here the 20 first such values:
Code:
185 or 187, x=31 (remainder=1)
245 or 247, x=41 (remainder=5)
425 or 427, x=71 (remainder=5)
473 or 475, x=79 (remainder=1)
533 or 535, x=89 (remainder=5)
581 or 583, x=97 (remainder=1)
713 or 715, x=119 (remainder=5)
833 or 835, x=139 (remainder=1)
869 or 871, x=145 (remainder=1)
893 or 895, x=149 (remainder=5)
1001 or 1003, x=167 (remainder=5)
1073 or 1075, x=179 (remainder=5)
1145 or 1147, x=191 (remainder=5)
1157 or 1159, x=193 (remainder=1)
1253 or 1255, x=209 (remainder=5)
1265 or 1267, x=211 (remainder=1)
1337 or 1339, x=223 (remainder=1)
1505 or 1507, x=251 (remainder=5)
1517 or 1519, x=253 (remainder=1)
1589 or 1591, x=265 (remainder=1)
This code will take a long time to process them all...