# Prime NUmbers

Page 1 of 1

## 3 Replies - 1415 Views - Last Post: 10 February 2009 - 08:10 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=85806&amp;s=2e00e09a53d9239c476c6cd219e67c2f&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 claretm

Reputation: 0
• Posts: 1
• Joined: 10-February 09

# Prime NUmbers

Posted 10 February 2009 - 04:50 AM

Hi All,

I have written a program to find all the prime numbers less than 1000000.
Can somebody help me to modify this code,so that I can get the biggest 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;
}
```

Thanks, gabehabe

Is This A Good Question/Topic? 0

## Replies To: Prime NUmbers

Reputation: 4
• Posts: 18
• Joined: 03-February 09

## Re: Prime NUmbers

Posted 10 February 2009 - 08:04 AM

Hi,

```#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";

int cnt = 0;			 // count gap size
int lgDiff[3] = {0}; // gap size, lower prime bound, upper prime bound

for (int i = 2; i <= N; i++)
{
cnt++;
if (prime[i]){
cout << i << endl;
if(cnt > lgDiff[0]){
lgDiff[0] = cnt; // gap between this prime and last prime is larger than previous gap
lgDiff[2] = i;   // get upper bound
}
cnt = 0;

}

}

lgDiff[1] = (lgDiff[2] - lgDiff[0]); // grab lower bound prime

cout << '\n';
cout << lgDiff[0] << '\n';
cout << lgDiff[1] << '\n';
cout << lgDiff[2] << '\n';

int a;
cin >> a;

return 0;
}

```

I got:

492227 - 492113

... close eh?

### #3 David W

• DIC supporter

Reputation: 256
• Posts: 1,669
• Joined: 20-September 08

## Re: Prime NUmbers

Posted 10 February 2009 - 07:58 PM

Quote

...I got: 492227 - 492113 ... close eh?

Nice code ... do you write it? Very cool approach

Shalom,
David

Reputation: 4
• Posts: 18
• Joined: 03-February 09

## Re: Prime NUmbers

Posted 10 February 2009 - 08:10 PM

David W, on 10 Feb, 2009 - 06:58 PM, said:

Quote

...I got: 492227 - 492113 ... close eh?

Nice code ... do you write it? Very cool approach

Shalom,
David

Yes, I wrote it. Thank you David.