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

  1. #1
    Registered User
    Join Date
    Dec 2009
    Posts
    32

    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;
    }
    Last edited by pantera; 12-23-2009 at 03:37 AM.

  2. #2
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,195
    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;
    	}
    Last edited by abachler; 12-23-2009 at 06:27 AM.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Hint: How many items are there in the primes vector just before this line?:
    Code:
    primes[0]=p;
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Getting an error with OpenGL: collect2: ld returned 1 exit status
    By Lorgon Jortle in forum C++ Programming
    Replies: 6
    Last Post: 05-08-2009, 08:18 PM
  2. Finding and Printing prime numbers using arrays
    By Sektor in forum C++ Programming
    Replies: 5
    Last Post: 12-11-2003, 08:29 PM
  3. Prime Numbers
    By cmangel518 in forum C++ Programming
    Replies: 13
    Last Post: 04-30-2002, 11:51 PM
  4. Homework help
    By Jigsaw in forum C++ Programming
    Replies: 2
    Last Post: 03-06-2002, 05:56 PM
  5. generating random numbers within a range
    By tucky in forum C Programming
    Replies: 3
    Last Post: 09-14-2001, 12:59 PM