• 07-15-2005
Antigloss
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; }```
• 07-15-2005
quzah
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.
• 07-15-2005
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; }```
• 07-15-2005
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:

```#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; }```
• 07-15-2005
quzah
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:

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.
• 07-15-2005
grumpy
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.