Thread: Finding prime numbers (Sieve of Eratosthenes): Range of Error --> where & how to fix?

1. Finding prime numbers (Sieve of Eratosthenes): Range of Error --> where & how to fix?

Hi,

I had to write this program based on the algorithm given at the beginning of the program. This program has a range of error, but I still can't figure out where & how to fix it. Could you please help?

Code:
```// Exercise 13 (Ch.4)
// Based on the Sieve of Eratosthenes algorithm provided on www.wikipedia.org
/*
1.	Create a list of consecutive integers from two to n: (2, 3, 4, ..., n).
2.	Initially, let p equal 2, the first prime number.
3.	Strike from the list all multiples of p greater than p.
4.	Find the first number remaining on the list greater than p (this number is the next prime);
Let p equal this number.
5.	Repeat steps 3 and 4 until p2 is greater than n.
6.	All the remaining numbers on the list are prime.

*/
#include "std_lib_facilities.h"

int square(int x)
{
return x*x;
}
int main()
{
vector<unsigned int>numbers;
vector<unsigned int>primes;
unsigned int n=100;
unsigned int i, p;

// Create a list of consecutive integers from 2 - n
for(i=2; i<=n;++i)
numbers.push_back(i);

p=2; // First prime number
primes[0]=p;
while(square(p)<=n) {

for(i=0;i<numbers.size();++i) {
if(numbers[i]>p && (numbers[i]%p)!=0)
primes.push_back(numbers[i]);
}
for(i=0;i<primes.size();++i) {
if(primes[i]>p) {
p=primes[i];
break;
}
}

}

for(i=0; i<primes.size();++i)
cout<<primes[i]<<endl;
}```

2. because you are taking powers of p instead of taking multiples of p.

Check out the prime number contest in the contest forum, I believe one of the entries was a sieve implementation.

here is a quicky version -
Code:
```#include <stdio.h>

#define PMAX 100

unsigned int Seive[PMAX];

int main(){
for(int i = 0;i<PMAX;i++) Seive[i] = i+2;

unsigned int Index = 0;
unsigned int p = 0;
unsigned int temp = 0;

while(Index < PMAX){
p = Seive[Index];
if(p == 0){
Index++;
continue;
}
printf("%d\n" , p);
temp = p + p;
while(temp < (PMAX + 2)){
Seive[temp-2] = 0;
temp += p;
}
Index++;
}

return 0;
}```

3. Hint: How many items are there in the primes vector just before this line?:
Code:
`primes[0]=p;`