C++ 计算质数的理解

质数（prime number）又称素数，有无限个。质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数的数称为质数。-- 来自“百度百科”

#include <iostream>
#include <iomanip>

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

int main()
{
    int max = 0;
    int count = 3;
    long trial = 5;
    bool isprime = true;

    cout << endl
         << "Enter the number of primes you would like: ";
    cin >> max;

    long* primes = new long[max];
    *primes = 2;
    *(primes + 1) = 3;
    *(primes + 2) = 5;

    do {
        trial += 2;
        int i = 0;

        cout << "trial is " << trial << endl;

        do {
            isprime = trial % *(primes + i) > 0;

            cout << "+++ trial is " << trial << " and i is " << i << " prime is " << *(primes + i) << endl;

        } while (++i < count && isprime);

        if (isprime) {
            *(primes + count++) = trial;

            cout << "add trial = " << trial << endl;
        } else {
            cout << "do not add trial = " << trial << endl;
        }
    } while (count < max);

    for (int i = 0; i < max; i++) {
        if (i % 5 == 0) {
            cout << endl;
        }

        cout << std::setw(10) << *(primes + i);
    }

    cout << endl;
    delete [] primes;
    primes = 0;

    return 0;
}

编译并运行，测试生成五个的输出如下：

➜  C g++ hello.cpp 
➜  C ./a.out       

Enter the number of primes you would like: 5
trial is 7
+++ trial is 7 and i is 0 prime is 2
+++ trial is 7 and i is 1 prime is 3
+++ trial is 7 and i is 2 prime is 5
add trial = 7
trial is 9
+++ trial is 9 and i is 0 prime is 2
+++ trial is 9 and i is 1 prime is 3
do not add trial = 9
trial is 11
+++ trial is 11 and i is 0 prime is 2
+++ trial is 11 and i is 1 prime is 3
+++ trial is 11 and i is 2 prime is 5
+++ trial is 11 and i is 3 prime is 7
add trial = 11

         2         3         5         7        11

从输出来看，大体的意思就是，首先看奇数，然后再挨个看能否被之前的质数整除，都不行的话，那就是新的质数。

• 例子代码参考自《C++入门经典》