By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,234 Members | 1,889 Online
Bytes IT Community
+ Ask a Question
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
  1. #include <iostream>
  2. using namespace std;
  3. int Check(int Prime[], int x)
  4. {
  5.     int j=2,t=0;
  6.     for (j=2;j<=x;++j)
  7.     {
  8.         if (j%2==0)
  9.             Prime[j]=0;
  10.         else
  11.             Prime[j]=j;
  12.         Prime[2]=2;
  13.         cout<<Prime[j]<<endl;
  14.     }
  15.     return Prime[j];
  16. }
  17. void main ()
  18. {
  19.     int i=0, Prime[100],n=0;
  20.     for (i=0;i<=99;++i)
  21.     {
  22.         Prime[i]=1;
  23.     }
  24.     cout<<"Please enter a number."<<endl;
  25.     cin>>n;
  26.     Check (Prime,n);
  27.  
  28. }
Jun 7 '07 #1
Share this Question
Share on Google+
4 Replies


Savage
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 <iostream>
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<<Prime[j]<<endl;
}
return Prime[j];
}
void main ()
{
int i=0, Prime[100],n=0;
for (i=0;i<=99;++i)
{
Prime[i]=1;
}
cout<<"Please enter a number."<<endl;
cin>>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
  1. for (int i= 2; i <= n; i++)
  2.    if (bit[i] is set)
  3.       for (j= i+i; j <= n; j+= i;)
  4.          wipeout(j);
  5.  
kind regards,

Jos
Jun 7 '07 #5

Post your reply

Sign in to post your reply or Sign up for a free account.