8
\$\begingroup\$

This is a program I wrote to print out 100 prime numbers. How can I improve it?

// Calculating primes
#include <iostream>
#include <iomanip>
#include <vector>
using namespace std;

int main()
{
    const int MAX(100);      // Number of primes to be identified
    long primes[MAX] = {};
    long trial(5);            // Hold a candidate prime
    int count(0);             // Count primes found
    bool found(false);      // Indicates when a prime is found

    vector <long> nonPrimes; //Vector to hold non prime numbers
    vector <long> disqualify; //Vector to hold prime numbers that disqualify the non prime numbers as prime numbers.

    do
    {
        trial += 2;             // Produce next candidate value
        found = false;      // Reset indicator - assume it is not prime

        for (int i = 0; i < count; i++)   // Try division by existing primes
        {
            found = (trial % primes[i]) == 0; // True if no remainder
            if (found) // No remainder means number is not a prime
                break;
            // Terminate the division loop
        }
        // The above loop will exit either due to a break or after trying all
        // existing primes as a divisor. found was initialized to false. If
        // found is false after exiting the loop, a divisor was not found.
        if (!found)             // We have a new prime: not false = true
            primes[count++] = trial;  // Save candidate in next array position
    } while (count < MAX);

    // Main loop has completed - we have found MAX prime numbers.
    // Display the prime numbers, presenting five numbers on one line.
    cout << "Prime numbers found during the program execution:" << endl;
    for (int i = 0; i < MAX; i++)
    {
        if (i % 5 == 0)      // For a new line on first line of output
            cout << endl;      // and on every fifth line that follows
        cout << setw(10) << primes[i];  // Provide space between numbers
    }

    cout << endl;            // All primes displayed - for a new line

    //system("pause");
return 0;
}
\$\endgroup\$
12
\$\begingroup\$
  1. STOP. Do not use system("pause"). This is not portable. If you haven't already, read this
  2. Stop using using namespace std. Read this. I mentioned this in your last review as well.
  3. You don't need to use std::endl for every new line of your output table. Doing so flushes the output stream needlessly.
  4. You don't need two vectors. Just two for loops and one vector will suffice. Take a look at the example below.
  5. For beginner code, I think you have good documentation(comments). Although for some people, it might err on the side of excessive.
  6. You could have initialized the array with the first three primes. That would have cut down the number of iterations.

     long primes[MAX] = {2,3,5};
     int count(0);             // Count primes found
    

Example:

#include  <iostream>
#include <vector>
#include <iomanip>

using std::cin;
using std::cout;
using std::endl;
using std::setw;


int  main()
{
    int counter = 0;
    std::vector<int> primes;

    int N, output;
    cin >> N;
    output = N;
    for (int i=2; N > 0; ++i)
    {
        bool  isPrime = true;
        for (int j=0; j < primes.size(); ++j)  //First pass(i==2), will not enter second loop because size() == 0
        {
            if (i % primes[j] ==  0)
            {
                isPrime = false;
                break;
            }
        }

        if (isPrime)
        {
            primes.push_back(i);
            --N;
            cout  <<  i  <<  "\n";
        }
    }


    for(int i=0; i < output; i++)
    {
        if (i % 5 == 0)      // For a new line on first line of output
            cout << "\n";      // and on every fifth line that follows

        cout << setw(10) << primes[i];  // Provide space between numbers
    }
    cout << endl;

    return  0;
}
\$\endgroup\$
  • 7
    \$\begingroup\$ 6. You could have initialized the array with first 25 numbers - that's all primes < 100 :) \$\endgroup\$ – Ixanezis Oct 13 '14 at 12:58
  • \$\begingroup\$ using namespace std; isn't a big deal with such a small program like this. With bigger programs I understand but there won't be any conflicting libraries here. \$\endgroup\$ – Chantola Oct 13 '14 at 13:09
  • \$\begingroup\$ I mention it whenever it pops up. Plus, this is tagged beginner. It's always good to stop a bad habit before it develops. \$\endgroup\$ – Quaxton Hale Oct 13 '14 at 21:24
  • \$\begingroup\$ @Chantola: Its not a problem but encourages a habit. This habit will come back to bite you in the long run. Best to always do it the better way and avoid the problem all together. \$\endgroup\$ – Martin York Oct 13 '14 at 22:31
  • \$\begingroup\$ the inner loop can be stopped when primes[j] * primes[j] > i. this will happen much sooner than the end of primes list. it doesn't matter for 100, yes, but even for 10K (or maybe 100K, still a small number) it will. \$\endgroup\$ – Will Ness Oct 14 '14 at 9:28
8
\$\begingroup\$

Let's talk about improvement of your code.

You know even numbers are never primes.
So a first step is to raise the for loop to i=i+2

Second, found = (trial % primes[i]) == 0;

This is correct but make 1 if before you do this :

The if should check if the square root of trial is lower then the prime number. If that is the case, you can abort your for loop cause no more matching results will be found.

\$\endgroup\$
  • \$\begingroup\$ +1 : You know even numbers are never primes. I never realised that. \$\endgroup\$ – Fahim Parkar Oct 13 '14 at 9:10
  • 1
    \$\begingroup\$ Except 2 is an even prime. \$\endgroup\$ – j.i.h. Oct 13 '14 at 13:25
  • 1
    \$\begingroup\$ @j.i.h. indeed :) \$\endgroup\$ – chillworld Oct 13 '14 at 14:05
  • 8
    \$\begingroup\$ 2 is the oddest prime! \$\endgroup\$ – Alexander Oct 13 '14 at 14:59
  • 1
    \$\begingroup\$ @FranciscoPresencia Next time, I will add quotation marks and half a dozen references, just for you! :) \$\endgroup\$ – Alexander Oct 14 '14 at 12:59
5
\$\begingroup\$

I'm surprised by the amount of code you've got for an ancient task. Please, use the Eratosthenes' sieve for this from now on - it's simpler and much more efficient (\$O(N log log N)\$ time complexity): (this code does not consider your special formatting)

#include <iostream>

int main() {
    const int MAX = 600; // Generates all primes below 600 - there's 109 of them
    bool mark[MAX] = {};
    for (int trial=2; trial<MAX; ++trial) {
        if (!mark[trial])
            std::cout << trial << '\n';
        for (int i=trial*trial; i<MAX; i+=trial)
            mark[i] = true;
    }
    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ The problem is I would be using Erathosthenes' sieve but I have no clue how I can implement it and your code looks like jargon in some parts. \$\endgroup\$ – Chantola Oct 13 '14 at 13:16
  • \$\begingroup\$ @Chantola: It isn't, but if you think so, you would want to step through with some debugger. Short description: mark is initialized as an array of boolean falses of length 100. Then, for i in 2..100, we print i if the i'th array position is unmarked, and mark all multiples of i. \$\endgroup\$ – Alexander Oct 13 '14 at 15:05
  • \$\begingroup\$ @Alexander let me rephrase that, it looks like jargon to me a (beginner) \$\endgroup\$ – Chantola Oct 13 '14 at 15:26
  • 3
    \$\begingroup\$ the OP asked for 100 prime numbers, not primes below 100... \$\endgroup\$ – Will Ness Oct 13 '14 at 18:38
  • \$\begingroup\$ @WillNess: Thanks, this algorithm has to be changed a bit to satisfy that. And thanks for the fix of the complexity - it's truly O(N log log N) @Chantola: If you follow the link in my answer, you'll probably find out that the algorithm is more straightforward than most of the code you find anywhere else. In addition, that's the very basics of computer science, something that programmers start with when learning (at least I did :) ). \$\endgroup\$ – Ixanezis Oct 14 '14 at 6:13
4
\$\begingroup\$

Everything was covered above, and...

  • You got way too many comments. Often it's claimed that code should be well commented. That's a lie. Truth is, every comment is a programmer's failure. They misinform, they rot, people tend to skip them. 98% percent of the time comments may be removed in favor to explanatory variables and methods.
  • Separating responsibilities is a common practice in software development. Now you wave mixed responsibilities is one method (main). There are definitely two (at least), generating numbers and printing them. Prime generator have no interest in knowing 'number printer', and NumberPrinter have no interest in knowing what kind of numbers (in this case, primes) it is printing
  • When you have multiple variables strictly related to each other is useful to encapsulate them in class (or maybe method for simple cases like this one). First of all, you limit scope of these variables. Moreover you hide implementation details from users. Third, it makes code easier to unit test. It would be nice to generatePrimes(int amount) without knowing implementation, would't it?

I would suggest structure similar to something like:

vector<int> generatePrimes(int amount){
    //generate primes here
}
void printNumbers(vector<int> numbers){
    //print numbers here
}
void main(){
    //take input parameters, whether std::cin or cmdline args
    vector<int> primes = generatePrimes(MAX_PRIMES);
    printNumbers(primes);
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy