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.  #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);


}
 
Share this Question
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
  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
 
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
  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): 
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
    Question stats  viewed: 1149
 replies: 4
 date asked: Jun 7 '07
