446,234 Members | 1,889 Online
Need help? Post your question and get tips & solutions from a community of 446,234 IT Pros & Developers. It's quick & easy.

# Another prime question

 P: 87 Hello everyone. I am writing a program which must print out prime numbers between 2 and a number entered by user. My code is below. Right now I am printing all odd numbers, but I can't seem to figure out how to get rid of numbers like 9,15,21, etc. any suggestions would be appreciated. Expand|Select|Wrap|Line Numbers #include  using namespace std; int Check(int Prime[], int x) {     int j=2,t=0;     for (j=2;j<=x;++j)     {         if (j%2==0)             Prime[j]=0;         else             Prime[j]=j;         Prime[2]=2;         cout<>n;     Check (Prime,n);   } Jun 7 '07 #1
4 Replies

 Expert 100+ P: 1,764 Hello everyone. I am writing a program which must print out prime numbers between 2 and a number entered by user. My code is below. Right now I am printing all odd numbers, but I can't seem to figure out how to get rid of numbers like 9,15,21, etc. any suggestions would be appreciated. #include using namespace std; int Check(int Prime[], int x) { int j=2,t=0; for (j=2;j<=x;++j) { if (j%2==0) Prime[j]=0; else Prime[j]=j; Prime[2]=2; cout<>n; Check (Prime,n); } It's because u are using j as array index,u should use other index which will only increase if conditon is fullfield.Also u should use nested loops. Savage Jun 7 '07 #2

 Expert 10K+ P: 11,448 Create a bit array of 'n' (or a bit more) bits where 'n' is the maximum number supplied by the user. Set all bits to one (1) except the first two bits. All bits act as a boolean flag: if bit i equals 1, i is supposed to be a prime number. Start at 2 and wipe out all multiples or two larger than two (4, 6, 8, etc). Move on to the next bit that is still equal to one (1). It's bit #3; wipe out all multiples of three larger than three (6, 9, 12, 15 etc.) Move to the next bit equal to one and do the same over and over again until you're at the 'n'th bit. This is the 'Sieve of Erasthostenes' algorithm. kind regards, Jos Jun 7 '07 #3

 P: 87 Hey Jos. Thanks for the suggestion. I've wiped out the multiples of 2. I guess I'm not quit sure how to take out the multiples of 3>3. The person right before you suggested a nested loop, but I don't know where to put it. Thanks, J Jun 7 '07 #4

 Expert 10K+ P: 11,448 Hey Jos. Thanks for the suggestion. I've wiped out the multiples of 2. I guess I'm not quit sure how to take out the multiples of 3>3. The person right before you suggested a nested loop, but I don't know where to put it. Thanks, J Something like this (in pseudo code): Expand|Select|Wrap|Line Numbers for (int i= 2; i <= n; i++)    if (bit[i] is set)       for (j= i+i; j <= n; j+= i;)          wipeout(j);   kind regards, Jos Jun 7 '07 #5