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.

## All 5 Replies

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

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 = false;  // 0 is not prime
prime = 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;
}
``````

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

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.

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.

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

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.