Thread: help about sieve algorithm

  1. #1
    C/C++Newbie Antigloss's Avatar
    Join Date
    May 2005
    Posts
    216

    help about sieve algorithm

    I wrote a program to print all the prime numbers from 1 to a given number, but this program is not efficient to deal with large number. Given a number such as 99999, it takes about 1min to finish this job. Could you please give me some suggestion on how to make this program more efficient? Thanks in advance.

    Code:
    #include <list>
    #include <vector>
    #include <iostream>
    #include <iomanip>
    
    using std::list;
    using std::vector;
    using std::cout;
    using std::cin;
    using std::endl;
    using std::setw;
    
    int main()
    {
    	list<unsigned long> numbers;
    	vector<unsigned long> prime;
    	unsigned long range;
    
    	// ask the user to input the range
    	cout << "I wanna know the prime numbers from 1 to : ";
    	cin >> range;
    	prime.push_back( 2L ); // 2 is the first one to sieve.
    	for ( unsigned long i = 3; i <= range; ++i ) {
    		if ( i % 2 ) { // multiples of 2 is no need to insert into the list
    			numbers.push_back( i );
    		}
    	}
    	
    	unsigned long tmp;
    	while ( !numbers.empty() ) {
    		tmp = numbers.front();
    		prime.push_back( tmp ); // push the first element of the list into the vector
    		numbers.pop_front(); // remove the first element from the list		
    		for ( std::list<unsigned long>::iterator iter = numbers.begin();
    		           iter != numbers.end(); ++iter ) {
    			if ( *iter % tmp ) {
    				continue;
    			}
    			iter = numbers.erase( iter ); // remove multiples of tmp from the list
    		}
    	}
    
    	// print the prime numbers
    	unsigned long j = 0;
    	for ( std::vector<unsigned long>::iterator it = prime.begin();
    	           it != prime.end(); ++it ) {
    		cout << setw(12) << *it << ' ';
    		if ( !(++j % 6) ) {
    			cout << '\n';
    		}
    	}
    	cout << endl;
    
    	return 0;
    }

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Well, you could get rid of all of the overhead you've got in your vector and list. Just use an array. It'll be less efficient memory wise, but it should be much faster. For starters, all you have to do is add the new prime to the end of the prime holding array. Just use a counter to keep track of the "top" of it, which you increment whenever you add a new one.

    Then all you do is walk the array and mod it with whatever the new number you're testing is.
    Code:
    for all the numbers you want to test
        for each number in the prime holding list
            if number to test mod the number in this spot in the array is zero
                break (this fails, so stop testing it)
        if the counter for the above loop equals the top of the prime list
            add this tested number to the end of the list and increment 'top'
    Oh, also, even with what you have there, and if you go the array method, increment by two, starting with the number 3, because you never need to test the numbers divisible by 2.


    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    Slave MadCow257's Avatar
    Join Date
    Jan 2005
    Posts
    735
    I just threw this together as an example. It can only handle very small numbers because the array will get too large. Also, you have to open the output file in wordpad, for some reason notepad doesn't work.

    Code:
    #include <iostream>
    #include <cmath>
    #include <fstream>
    
    #define MAX 99999
    
    using namespace std;
    
    int main()
    {
    	int array[MAX];
    	int loopmax = sqrt(MAX);
    	int current = 2;
    	int whilevar2;
    	while (current <= loopmax)
    	{
    		if (array[current] != -1)
    		{
    			whilevar2=2*current;
    			while (whilevar2 < MAX)
    			{
    				array[whilevar2] = -1;
    				whilevar2 = whilevar2 + current;
    			}
    		}
    		current++;
    	}
    	current = 2;
    	ofstream out;
    	out.open("Output.txt");
    	while (current < MAX)
    	{
    		if (array[current] != -1)
    			out << current << " ";
    		current++;
    	}
    	out.close();
    	return 0;
    }

  4. #4
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    I wouldn't do it with two loops, for starters. The following is untested, but intended to show the general approach I would try to use ....

    Code:
    #include <vector>
    #include <iostream>
    #include <iomanip>
    
    using std::vector;
    using std::cout;
    using std::cin;
    using std::endl;
    using std::setw;
    
    typedef std::vector<long>::iterator prime_iterator;
    
    int main()
    {
    	vector<unsigned long> prime;
    	unsigned long range;
    
    	// ask the user to input the range
    	cout << "I wanna know the prime numbers from 1 to : ";
    	cin >> range;
    	prime.push_back( 2L ); // 2 is the first one to sieve.
            prime.push_back( 3L);
    	for ( unsigned long i = 3; i <= range; i += 2)
           {
               bool not_prime = true;
               for (prime_iterator j = prime.begin() + 1; not_prime && j != prime.end(); ++j)
               {               
    		not_prime = ((i % (*j)) == 0);
               }
                if (not_prime) prime.push_back(i);
            }
    	
           
           for (prime_iterator i = prime.begin(), end = prime.end(); i != end; ++i)
           {
              for (j = 0; j < 5 && i != end; ++j, ++i)
              {
                    cout << setw(12) << *i;
              }
              cout << '\n';
           }
    	return 0;
    }

  5. #5
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by grumpy
    I wouldn't do it with two loops, for starters. The following is untested, but intended to show the general approach I would try to use ....

    Code:
    	for ( unsigned long i = 3; i <= range; i += 2)
           {
               bool not_prime = true;
               for (prime_iterator j = prime.begin() + 1; not_prime && j != prime.end(); ++j)
               {               
    		not_prime = ((i % (*j)) == 0);
               }
                if (not_prime) prime.push_back(i);
            }
    What was that about not using two loops?

    Quote Originally Posted by MadCow257
    Code:
    int array[MAX];
    	int loopmax = sqrt(MAX);
    	int current = 2;
    	int whilevar2;
    	while (current <= loopmax)
    	{
    		if (array[current] != -1)
    You never initialize your array to anything, so it's possible for the random garbage that's in there already to actually equal -1 in a spot where a prime would fall. Very slight chance, but possible. A quick fix...
    Code:
    int array[MAX] = {0};

    Quzah.
    Hope is the first step on the road to disappointment.

  6. #6
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    Quote Originally Posted by quzah
    What was that about not using two loops?
    The code in the original post used one loop to get a set of odd numbers, and then another to test if those odd numbers are prime.

    Basically, my intent was to roll those into one loop.

    But, you're right, any solution to compute multiple primes requires a nested loop.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 02:30 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  4. sieve of Erotosthenes (HELP!!!)
    By JFK in forum C Programming
    Replies: 1
    Last Post: 02-19-2002, 12:53 PM