**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:

`x`is

*ODD*) | checks if passed parameter

`x`is a prime. returns

*TRUE*if

`x`is prime,

*FALSE*otherwise

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:

`x`is

*not divisible by 2 or 3*) | checks if passed parameter

`x`is a prime. returns

*TRUE*if

`x`is prime,

*FALSE*otherwise

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:

`floor(100/2) + floor(100/3) - floor(100/6) = 50 + 33 - 16 = 67`per

*100*

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.

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!