Printing 100 prime numbers

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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

Answer 4

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