C program to find Twin Prime Numbers

In this article, we have explored the approach to find twin prime numbers less than N and implement it in C Programming Language.

Table of contents:

1. Introduction to Prime Numbers and Twin Prime
2. Approach
3. C program to find Twin Prime Numbers
4. C program to find Number of Twin Primes

Introduction to Prime Numbers and Twin Prime

Prime Number is a Natural Number which has only two factors that is 1 and itself. In other words, prime numbers are not exactly divisible (a remainder of 0) by any other numbers.

Example of prime numbers = 2, 3, 5, 7, 11, 13, 17 and so on.

Twin Prime Number is a prime number N such that either N-2 or N+2 is a prime number. In other words, when two consecutive odd numbers are primes, these are known as twin prime numbers.

Example of twin prime numbers = 3 and 5; 5 and 7; 11 and 13; 17 and 19 and so on.

Approach

The approach to find twin prime numbers less than N is as follows:

1. Generate the list L of prime numbers less than N. Let there be M such primes.
2. Traverse the list L and check the difference between each consequetive prime numbers.
   2.1. If the difference is 2, then the two prime numbers are twin prime numbers.
   2.2. These two prime numbers are saved in the list of twin prime numbers and the count of twin prime numbers is incremented.

To understand this better, go through the following:

• Sieve of Erathones
• Time Complexity Analysis of Sieve of Erathones

Time and Space Complexity

One can generate the list of prime numbers less than N is O(N loglogN) time complexity by Sieve of Erathones. The number of prime numbers is approximately O(N/ logN).

So, checking each adjacent pair of prime numbers for twin prime numbers have O(N/logN) time complexity.

This results in an overall time complexity of (N loglogN + N/logN) ~= O(N loglogN).

The same complexity is O(N/logN) as we store all prime numbers less than N.

In summary:

• Time Complexity: O(N loglogN)
• Space Complexity: O(N/logN)

C program to find Twin Prime Numbers

In C implementation, we define two major functions:

• sieve_of_eratosthenes(): To generate the list of prime numbers less than N
• findTwinPrimes(): To find the twin primes from the above list of prime numbers.

There are 3 main arrays:

• isPrime: Size is N. This is used by sieve_of_eratosthenes() to find all prime numbers according to its algorithm.
• primes: Size is number of prime numbers (M). This is the result from sieve_of_eratosthenes().
• twin_primes: For simplicity, the size is same as primes array but in reality, it can be reduced. We keep a count of twin primes. This is the output of the function findTwinPrimes().

Following is the C program to find Twin Prime Numbers:

#include <stdio.h>
#include <stdlib.h>

int sieve_of_eratosthenes(int **primes, const int max) {
	// Allocate memory
	int *isPrime = (int *)malloc(sizeof(int) * (max + 1));
	int i;
	// Assume all numbers to be prime initially
	for(i = 0; i <= max; ++i)
		isPrime[i] = 1;
	// 0 and 1 are not prime
	isPrime[0] = 0;
	isPrime[1] = 0;
	// Maintain a count of primes as we encounter them
	int count = 0;
	// We need a count of all primes as we move
	// This means we cannot iterate to root(max)
	for(i = 2; i <= max; ++i)
	{
		if(isPrime[i] == 1)
		{
			++count;
			int j;
			// Set all multiples of i as not prime
			for(j = 2 * i; j <= max; j += i)
				isPrime[j] = 0;
		}
	}
	*primes = (int *)malloc(sizeof(int) * count);
	int j = 0;
	for(i = 0; i <= max; ++i)
	{
		if(isPrime[i] == 1)
		{
			(*primes)[j++] = i;
		}
	}
	return count;
}

int findTwinPrimes(int **primes, int **twin_primes, const int size) {
    int count = 0;
    *twin_primes = (int *)malloc(sizeof(int) * size);
    
    for(int i = 0; i < size-1; ++i)
	{
	    if((*primes)[i+1] - (*primes)[i] == 2) {
	        (*twin_primes)[count++] = (*primes)[i];
	        (*twin_primes)[count++] = (*primes)[i+1];
	    }
	}
	count = (int)(count/2);
	return (int)(count);
}


int main() {
	int n = 10000, i;
	int *primes = NULL;
	int *twin_primes = NULL;
	// Find primes up to n
	int size = sieve_of_eratosthenes(&primes, n);
	
	int twin_prime_size = findTwinPrimes(&primes, &twin_primes, size);
	
	printf("Twin Primes up to %d are:\n", n);
	for(i = 0; i < twin_prime_size*2;)
	{
		printf("%d, %d\n", twin_primes[i], twin_primes[i+1]);
		i = i + 2;
	}
	return 0;
}

Output:

Twin Primes up to 500 are:
3, 5
5, 7
11, 13
17, 19
29, 31
41, 43
59, 61
71, 73
101, 103
107, 109
137, 139
149, 151
179, 181
191, 193
197, 199
227, 229
239, 241
269, 271
281, 283
311, 313
347, 349
419, 421
431, 433
461, 463

C program to find Number of Twin Primes

To find the number of twin primes only, add this code line:

printf("Number of Twin Primes up to %d are %d\n", n, twin_prime_size);

Update the main function as follows to find the number of twin primes less than a given number:

int main() {
    for (int n=10; n <= 10000000; n=n*10) {
        int i;
        int *primes = NULL;
        int *twin_primes = NULL;
        // Find primes up to n
        int size = sieve_of_eratosthenes(&primes, n);
        int twin_prime_size = findTwinPrimes(&primes, &twin_primes, size);
        printf("Number of Twin Primes up to %d are %d\n", n, twin_prime_size);
    }
	return 0;
}

Output:

Number of Twin Primes up to 10 are 2
Number of Twin Primes up to 100 are 8
Number of Twin Primes up to 1000 are 35
Number of Twin Primes up to 10000 are 205
Number of Twin Primes up to 100000 are 1224
Number of Twin Primes up to 1000000 are 8169
Number of Twin Primes up to 10000000 are 58980

With this article at OpenGenus, you must have the complete idea of how to find twin primes and number of twin primes less than a given number in C Programming Language.