Twin Prime: A twin prime is a set of two prime numbers whose absolute difference is 2. Let p1 and p2 primes such that p2 – p1 = 2, then the set { p1 , p2 } are twin primes.
Objective Of The Article
The objective of this article is to describe the basic algorithm to search for the twin primes first, and then make some modifications to make it better and faster. At last we present the final code
Article Revision: 2
Article Index
- Twin Prime: Definition
- Objective Of The Article
- The Basic Process
- The Faster Process
- The Difference
- Cousin Primes
- Sexy Primes
- Download Source Code
- This Is Not The End
The Basic Process
The basic idea is to check first, if i and (i + 2) both are primes, then the set of two integers { i , (i+2) } is a twin prime. When testing the two integers for prime if one of them is found is not a prime then we skip that integer and check the next. i belongs to the set of positive integers. This process is repeated / iterated by incrementing i by 2 in each iteration. To check if an integer is prime or not, a divide and check algorithm can be used. This process will be divided in two routines, one will generate the i and (i + 2), implemented as the “main()” routine, and the “isprime()” function will check if the passed integers from the main() routine is prime or not.
Algorithm for the main() function:
WHILE 'i' is within range
IF ( isprime(i) AND isprime(i+2) ) both are true, THEN
New twin prime set found: { i , (i+2) }
INCREMENT 'i': 'i'='i+2'
END of while loop
C Language code for main() function:
/*The main function*/
int main(void)
{
int i=5,count=1,n;
printf("\nEnter range:");
scanf("%d", &n);
/* Adjust n to give output inside range */
n-=2;< /*Print the first set manually, because 3 will be returned as a nonprime*/
printf(" { %ld , %ld },", 3 ,5);
while(i < n)
{
if( isprime(i) && isprime (i+2) )
{
/*we have found a new twin prime set { i , i+2 }*/
printf(" { %ld , %ld },", i ,i +2);
count++;
}
i=i+2;
}
printf("\nTotal: %d",count);
return 0;
}
Description:
i has been initillized with 5, the fist prime integer of the second twin prime set { 5 ,7 }. The loop runs till i is within the range, n. i is incremented by 2 in each iteration. The current value of i and (i + 2) are checked for primes in each iteration with the isprime() function. If an integer is prime isprime() returns TRUE else it returns FALSE. When both are primes, isprime() returns TRUE for both integers and the if statement becomes true and a new set of twin prime is found. If isprime() returns FALSE for any one integer that, the “if” statement is false and no twin prime is found, control goes to next iteration.
Now we describe the isprime() function. Detailed discussions about prime check algorithm is avoided here to stick to our objective, though we will describe the isprime() function after we present the algorithm and the C Language source code of it.
Algorithm for isprime() function:
IF 3 divides 'x' RETURN false INITILIZE 'i' with '5' WHILE 'i' is less than equal to sqrt(x), DO IF 'i' divides 'x', THEN RETURN false INCREMENT 'i' : 'i'='i+2' END of while loop RETURN true
C Programming Language code for the isprime() function:
/*The isprime function*/
int isprime (long int x)
{
long int i;
/*if x is divisible by 3 return false*/
if(x%3==0)
return FALSE;
/*initialize i with 5, start dividing x with i, increment i to 2
*after each iteration. If any one the values of i divides n, return false
*representing n is not a prime*/
for(i=5;i< =sqrt(x);i+=2)
if(x%i==0)
return FALSE;
/*return true if the for loop terminates, i.e x is prime*/
return TRUE;
}
Description:
isprime() receives a long integer type argument, x, which it tests for prime. The function assumes x to be odd, so it is made sure main() passes only odd integers while calling isprime(). If x is found to be a prime (no i divides x),TRUE is returned, otherwise FALSE is returned. x is first checked if divisible by 3, if not then the loop checks x if divisible with any integer between 5 and sqrt(x) (including both). If x is not a prime (divisible), that is when the “if” statement becomes true, FALSE is returned to the calling function immidiately. If none of the integers divide x, that is, when the “if” statement is never true, the loop terminates, and TRUE is returned.
Note: x is not divided with 2, because isprime() assumes only odd integers are passed, so x%2 would always be non-zero. If any even integer is passed this function will return it is a prime. It is to be made sure that the passed integer is odd, when calling the function
The preprocessor directives:
/*Preprocessor directives*/ #include "stdio.h" #include "math.h" #define TRUE 1 #define FALSE 0
Download above code here (C Language)
Combining the isprime() and the main() function twin prime sets can be generated, but this technique can be optimized for faster output. The above process skips multiple of 2s and passes only odd integers. Only odd integers are used to divide and check x in isprime() function. The above process will be optimized by skipping the multiples of 2s as well as the multiple of 3s too in both functoins. Notice that the divition by 3 is separate from the loop in the above program, this is done so that the changes in the code for the optimization just told can be implemented easily. Read the next section to know how to use make this optimization.
The Faster Process
This optimized method is basically same as the previous method, two integers i and (i+2) are checked if both are primes and finds the twin prime set. This process has a change in the incremental part of i in both main() and isprime() functions. Previously, i was initilized with 5 and incremented by 2 in each iteration, thus i only generated odd integers in main() which passed into isprime(), and in isprime() odd integers were generated to divide the passed integer and check if it is prime. Now we will generate i in both the functions such that it is not a multiple of 2 or 3 (or both). Doing this , no multiple of 3s will be passed into isprime() from main(), and also no multiple of 3 will be used to divide the passed integer in isprime(). This will save a lot of computation.
The task is to generate a series of integers which are not a multiple of 2 or 3 (or both). Below we show the series whose integers are not a multiple of 2 or 3.
5 , 7 , 11 , 13 , 17 , 19 , 23 , 25 , 29 , 31 , 35 , 37 , 41 , 43 , 47 , 49 ....
The absolute differences of two adjacent integers are observed as shown below:
2 , 4 , 2 , 4 , 2 , 4 , 2 , 4 , 2 , 4 , 2 , 4 , 2 , 4 , 2 ....
The absolute difference of two adjacent numbers of the series is an alternating sequence of 2 and 4. It is clear that starting with 5 and adding 2 and 4 alternatingly with the last sum, the required series can be generated. Now we will write the code which will generate the differences, that is the alternating sequence of 2 and 4, then the difference values in each step will be added with the current value of i to get the next integer of the series (with no multiple of 2 or 3). Check the code snippet below
/*n is the upper limit*/
int dx=4,i=5,n;
while(i< =n)
{
printf("%d",i);
/* Generates the the difference, *
* the alernating 2 and 4 sequence */
dx=-(dx-6);
/* Adds the generated difference 'dx' with *
* with the current value of 'i' to get the *
* next value of the series with no multiple *
* of 2 and 3 */
i=i+dx;
}
The above code generates the required series which generates integers which are not multiple of 2 or 3. The first expression dx -= (dx-6), with dx initilized to 4, generates the next difference, then the expression i = i+dx, with i initilized to 5, adds the next difference dx (just generated)
, to the current value of i and generates the next value of the required series. At the end of each iteration we get a new value of the required series, which is not divisible by 2 or 3, which we can use in the main() and the isprime() functons.
For ease a sample run of the above code snippet is shown below:
- dx is 4 at beinning. The new value of dx -> dx=-(dx-6) : (-(4 – 6)) = 2
Next value of i -> i = i + dx : (5 + 2) = 7 - Current value of dx is 2
The next value of dx -> dx=-(dx-6) :(-(2 – 6)) = 4
The next value of i -> i = i + dx : 7 + 4 = 11 - In the next iteration dx = (-(4 – 6)) = 2 and i = (11 + 2) = 13 and so on.
Now we start modifications to the functions we presented in the previous section. First isprime() and then main() will be modified.
Modification in isprime()
The first divition with 3 check can be safely omitted, because isprime() only recieves integers which are not multiples of 2 or 3.
if(x%3==0) return FALSE;
The above code can be removed.
Note: Omitting this statement is safe if and only if multiples of 2 or 3 are not passed, because the isprime() assumes passed integers are not multiple of 2 or 3. If isprime is called with an integer, multiple of 2 or 3 or both for example 48, it will show 48 is a prime.
The modified loop structure of isprime() function is shown below.
i=5
while(i< =sqrt(x)) {
if(x%i==0) {
return FALSE;
}
dx=-(dx-6);
i=i+dx;
}
return TRUE;
Note how the code to generate the series discussed above is integrated into the while loop. Below the same loop is presented in “for” loop syntax:
for( i = 5 ; i < = sqrt(x) ; dx =- (dx - 6), i += dx ) {
if(x%i==0) {
return FALSE;
}
}
return TRUE;
Modification in main()
Modification in the main() function needs slight adjustment in the increment part as illustrated below.
i=5;
while(i < n)
{
if(isprime(i) && isprime(i+2)) {
printf(" { %d , %d }",i,i+2);
/*A new twin prime set is found;*/
}
/*increment i to the next integer not divisible by 2 or 3*/
i=i+6;
}
Why i is incremented by 6 is described as follows: In function main(), two adjacent integers in the series (of which no integer is divisible by 2 or 3), with absolute difference of 2, i and (i+2) are checked for primes. The next value of i will have absolute difference of 4 with the last value (i+2), therefore the next value of i will be ( (i+2) + 4 ) = (i+6)
The above diagram can be inspected to see how the comparisons and the increments are made
- The blue rectangles represent a single iteration.
- In each iteration the green circle represents the value of i for that iteration.
- The black lines represent the two integers pointed with it has a difference of two and they are checked for primes.
- The red lines represent the value of i for the next iteration is iteration by adding 6 to the current value of i.
Note: The first twin prime set, { 3 , 5 } cannot be generated with this method. This can be printed or enumerated manually.
Optimized algorithm for main() function:
WHILE 'i' is within range
IF ( isprime(i) AND isprime(i+2) ) both are true, THEN
New twin prime set found: { i , (i+2) }
INCREMENT 'i' : 'i'='i+6'
END of while loop
Optimized algorithm for isprime() function:
INITIALIZE 'i' with 5
INITIALIZE 'dx' with 4
WHILE 'i' is less than equal to sqrt(x), DO
IF 'i' divides 'x' , THEN
RETURN false
ADJUST 'dx' with: 'dx' = '-(dx-6)'
INCREMENT 'i' : 'i'='i+dx'
END of while loop
RETURN true
Optimized version C Language code to generate twin prime integers
#include "stdio.h"
#include "math.h"
#define TRUE 1
#define FALSE 0
int isprime(long int x);
int main(void)
{
long int i,n,count=1;
printf("\nEnter Range: ");
scanf("%ld",&n);
if(n >=3)
printf(" { 3 ,5 },");
for(i=5;i+2< =n;i+=6)
if(isprime(i)&&isprime(i+2))
{
printf(" { %ld , %ld },",i,i+2);
count++;
}
printf("\b \n\nTotal Primes within range: %ld\n",count);
return 0;
}
int isprime(long int x)
{
long int max=(int)sqrt(x),i,dx=4;
for(i=5;i<=max;dx=-(dx-6),i+=dx)
if(x%i==0)
return FALSE;
return TRUE;
}
Download above code here (C Language)
The first set of twin prime is printed manually with a condition which is if the range is entered 3, or lesser then it won’t be printed. Though it is unnecessary, it can be kept to stop bug finders. Again note the isprime() function is not universal, if an integer is divisible by 2 or 3 or both is passed, the function will return it as a prime, because this assumes the calling function only passes integers which are not divisible by 2 or 3 or both, thus avoids divitions with 2 and 3.
The Difference
How much we get by skipping divitions by multiple of 2 and 3 ? Check out the below analisys.
- There are floor(100/2)=50 integers divisible by 2 per 100.
- There are floor(100/3)=33 integers divisible by 3 per 100, and
- There are floor(100/6)=16 integers divisible by 2 and 3 both (ie 6) per 100.
The total number of integers per 100 avioded is:
That is 67% of integers are avoided with the optimized process. The first process skipped 50% of integers. The optimized process avoids 17% more integers by skipping multiples of 3s. You can see the difference on your own. Comment the “printf” and “scanf” statements in the main() function and initilize n with some high value and run the two versions. Use the time command in Unix/Linux to time the output. Run as below time program_name and check the time taken with both versions.
Cousin Primes
A cousin prime is a set of two prime numbers whose absolute difference is 4. Let p1 and p2 primes such that p2 – p1 = 4, then the set { p1 , p2 } are cousin primes.
A cousin prime set can be generated just like the twin primes. A slight modification to the source code of twin prime is done to make a program to generate cousin primes.
The changes in the ‘faster process’ code are:
- Replace isprime(i+2) with isprime(i+4)
- Replace printf(" { %d , %d },",i,i+2); with printf(" { %d , %d },",i,i+4);
- Initilize i with 7
- Manually print the first cousin prime set { 3 , 7 }
The changes are shown below:
if(n>=3)
printf(" { 3 , 7 },");
for(i=7;i+2< =n;i+=6) {
if(isprime(i) && isprime(i+4)){
printf(" { %d , %d },",i,i+4);
count++;
}
}
The changes for the source code of ‘basic process’ it is only needed to replace the (i+2) in the “printf” and isprime() function call in the “if” statement with (i+4)
Download above code here (C Language)
Sexy Primes
A sexy prime is a set of two prime numbers whose absolute difference is 6. Let p1 and p2 primes such that p2 – p1 = 6, then the set { p1 , p2 } are sexy primes.
A sexy prime set can be generated just like the twin primes. The modifications in the above program to generate sexy primes is a bit different than in cousin primes. We check if i and (i+6) are primes. Then instead of incrementing i to 6, we increase i with 2 and 4 alternatingly, like in isprime() function. Because i and (i+6) is not divisible by 2 or 3 there is one integer between these two which is also not divisible be 2 or 3, and it is (i+2) or (i+4) alternatingly for each i. That integer is needed to be considered. So i needs to be incremented by 2 and 4 alternatingly in each iteration.
The changes in the ‘faster process’ source code will be:
- Replace isprime(i+2) with isprime(i+6)
- Replace printf(" { %d , %d },",i,i+2); with printf(" { %d , %d },",i,i+6);
- Replace the increment part of “for” loop with dx=-(dx-6),i+=dx
- Initilize i with 5
The changes are shown below:
for(i=5,n-=2;i< =n;dx=-(dx-6),i+=dx) {
if(isprime(i) && isprime(i+6)) {
printf(" { %d , %d },",i,i+6);
count++;
}
The changes for the source code of ‘basic process’ it is only needed to replace the (i+2) in the “printf” and isprime() function call in the “if” statement with (i+6)
Download above code here (C Language)
Download Source Code
Download All source codes of the above programs Here
Contents of the archive
- Source Code of Twin Prime, basic method
- Source Code of Twin Prime, optimized method
- Source Code of Cousin Prime
- Source Code of Sexy Prime
This Is Not The End
Though we do not allow to generate multiples of 2 and 3, multiples of 5,7,11 and the other primes are generated and creates unnecessary computations. The best to determine prime by division is only to divide the integer with only prime integers lesser that sqrt(x). This can be done by generating primes and then storing them in memory as needed, and diving the integer in question sequentially with the numbers stored in list. This will make the algorithm more efficient and faster, but would require a more memory for larger limits. But if a careful design is done and only those prime numbers are stored which we need then the memory requirement will decrease.
Phoxis 
hmmmm,very very sexy
hey the comment before mine seems a bit different.
who is that guy who find prime numbers “sexy”!!!!!!?????
may god bless him!