C Program to find the largest difference between two prime numbers.

[claretm]

Hi All,

The gap between consecutive prime numbers 2 and 3 is only 1, while the gap between consecutive primes 7 and 11 is 4. Can somebody help me in writing a parallel program to determine, for all integers less than 1,000,000 , the largest gap between a pair of consecutive prime numbers.

[WaltP]

Start by writing a program to determine the prime numbers less than 1,000,000. Then modify the program to test the differences.

[claretm]

Thanks for the reply.
If this gives all the prime numbers less than 1000000,how can i modify this to get the largest difference between two consecutive prime numbers?

#include <iostream>
#include <cmath>
using namespace std;

int main ()
{
    const int N = 1000000;
    const int SQR_ROOT_N = (int) (sqrt ((double) N));
    bool prime[N + 1];

    prime[0] = false;  // 0 is not prime
    prime[1] = false;  // 1 is not prime

    for (int i = 2; i <= N; i++)
         prime[i] = true;  // flag all numbers as prime initially

    for (int i = 2; i <= SQR_ROOT_N; i++)
    {
        if (prime[i]) // no need for inner loop if i is not prime
        {
            for (int j = 2 * i; j <= N; j+=i)
                 prime[j] = false;  // j is a multiple of i, thus not prime.
        }
    }

    // display prime numbers
    cout << "Here are the prime numbers\n\n";
    for (int i = 2; i <= N; i++)
    {
        if (prime[i])
            cout << i << endl;
    }

    return 0;
}

[csurfer]

Thanks for the reply.
If this gives all the prime numbers less than 1000000,how can i modify this to get the largest difference between two consecutive prime numbers?

Well you need to know one thing very clearly that your program is not generating prime numbers up to 1000000 as you have mentioned. Your program just generates prime numbers till 1000 i,e sqrt(1000000).

And to find the max this is what you need to do:

int i=2,j=3,max=0;

// Setting two variables i and j to first two prime numbers
// Setting max difference to 0 to start with

while( j <= N ) // To ensure higher prime doesn't go beyond N
{
        if( (j-i) > max )   //If this difference > Present max value
                      max=j-i;   //Assign this difference to max 
        
        i=j;   //Shifting i's value to next prime i,e j 
        j++; //Increment j by 1 so that its value changes
 
        while( prime[j] != true && j < N ) j++;
        // Move j's value till it reaches next prime or N
}

printf("Maximum Difference between consecutive prime numbers is %d",max);

Hope you can get the above code.(Its quite cumbersome) This will definitely do your work.

[WaltP]

Hope you can get the above code.(Its quite cumbersome) This will definitely do your work.

Hope you get a good grade for the program, csurfer.
claretm certainly doesn't deserve it.

[claretm]

Hi csurfer,
Thanks a lot for the solution.It definitely works.