roman10
The previous two posts cover the naive approaches for primality testing and a method with precomputation. This post introduces a new method which could perform better than previous approaches and it can be used together with the precomputation.
The optimization is based on the observation that all prime numbers are in the form of 6k+1 or 6k+5, with 2, 3 and 5 being the only exceptions. This is because all integers can be expressed in 6k+i for some integer k, and i is from the set {0, 1, 2, 3, 4, 5}. And 2 divides 6k+0, 6k+2 and 6k+4, 3 divides 6k+3.
Therefore, the primality test for a given integer n can be done by checking if n is divisible by 2 and 3 first, and then checking if n is divisible for all numbers of form 6k+1 or 6k+5 and less than sqrt(n).
The idea of this optimization is actually similar to the Sieve of Eratosthenes algorithm described in previous post. We eliminated testing divisibility for numbers that is divisible by the prime factors.
In general, all prime numbers are in the form gk + i, where i < k and it represents the numbers that are coprime to g. In the case above, g = 6 and the coprime of 6 are 1 and 5. If i and g are not coprime, then i must be divisible by some prime factors of g.
We go through another example, suppose g = 2*3*5 = 30, then all integers can be expressed in the form 30*k + i where i is in the set {0, 1, 2….29}. Now we mark the numbers that divisible by 2, 3 and 5 respectively. 30*k + {0, 2, 4, 6, 8, 10, 12, …28} are divisible by 2; 30*k + {3, 6, 9, 12, 15, 18, 21, 24, 27} are divisible by 3; and 30*k + {5, 10, 15, 20, 25} are divisible by 5. The rest of the numbers {1, 7, 11, 13, 17, 19, 23, 29} are not divisible by 2, 3 and 5 and are therefore coprimes of 30.
So to test if a number n is prime number, we first test if the number is divisible by 2, 3, and 5 first, and then check if the number is divisible by numbers in the form 30*k + {1, 7, 11, 13, 17, 19, 23, 29} up to sqrt(n).
Below is an implementation of the optimization for primality testing when g is set to 6,
/**
generate prime numbers
**/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int rdiv(int n, int m) {
if (n%m ==0) {
printf("%d is divisible by %d\n", n, m);
return 0;
}
return 1;
}
int prime(int n) {
int i, k, ed, m;
int cpr[2] = {1, 5};
//check if we can divide the prime factors first
if (n == 2 || n == 3) {return 1;}
if (rdiv(n, 2) == 0) {
return 0;
} else if (rdiv(n, 3) == 0) {
return 0;
}
//printf("ifprime: %d", ifprime);
//check up to sqrt(n) of the form 6k + {coprime of 6}
ed = sqrt(n) + 1;
for (k = 0; ;++k) {
for (i = 0; i < 2; ++i) {
m = 6*k + cpr[i];
if (m < 3) {continue;}
if (m > ed) {
return 1;
}
if (n%m == 0) {
printf("%d is divisible by %d\n", n, m);
return 0;
}
}
}
return 1;
}
int main(int argc, char **argv) {
int n = atoi(argv[1]);
int i;
struct timeval stTime, edTime;
gettimeofday(&stTime, NULL);
if (prime(n)) {
printf("%d is prime number\n", n);
} else {
printf("%d is not prime number\n", n);
}
gettimeofday(&edTime, NULL);
printf("time: %u:%u\n", (unsigned int)(edTime.tv_sec - stTime.tv_sec), (unsigned int)(edTime.tv_usec - stTime.tv_usec));
return 0;
}
Save the code to prim4.c and compile the code with command below,
gcc -o prim4 prim4.c –lm
Below are some simple tests:
roman10@ra-ubuntu-1:~/Desktop/integer/prim$ ./prim4 2
2 is prime number
time: 0:49
roman10@ra-ubuntu-1:~/Desktop/integer/prim$ ./prim4 3
3 is prime number
time: 0:62
roman10@ra-ubuntu-1:~/Desktop/integer/prim$ ./prim4 5
5 is prime number
time: 0:52
roman10@ra-ubuntu-1:~/Desktop/integer/prim$ ./prim4 2147483647
2147483647 is prime number
time: 0:267
roman10@ra-ubuntu-1:~/Desktop/integer/prim$ ./prim4 2147483641
2147483641 is divisible by 2699
2147483641 is not prime number
time: 0:72
Note that the code can be further improved by adding the pre-computation we mentioned in part2.
If you enjoyed this article, please consider sharing it!
