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;
}

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;
	}

Hint: How many items are there in the primes vector just before this line?:

Code:

primes[0]=p;