C++大学教程（第九版）6.29素数

题目

(素数)素数是只能被1和自已整除的整数。例如,235和7是素数而468和9不是素数
a)编写一个函数，确定一个数是否是素数。
b)在程序中使用这个函数，该程序确定和打印2 ~10000之间的所有素数。在确信已找到所有的素数之前，实际需测试这些数中的多少个数?
c)起初，你可能认为 n/2 是确定一个数是否为素数所要进行的最多的测试次数，但是实际上只需要进行n的平方根次就可以了。为什么呢?重新编写程序，用这两种方式运行。估计性能提高了多少。

b)代码

b)实际需要测试这些数中的5000个，满足条件的代码如下：
增加了计算程序运行时间的部分。

#include <iostream>
#include <iomanip>
#include <ctime>
using namespace std;

bool isPrime(int);

int main()
{
    clock_t startTime, endTime;
    startTime = clock();
    int count = 0;
    for (unsigned long long i = 2; i <= 10000; i++)
    {
        if (isPrime(i))
        {
            cout << setw(4) << i << "\t"; //<< (isPrime(i) ? "是素数" : "")
            count++;
            if (count != 0 && count % 10 == 0)
            {
                cout << endl;
            }
        }
    }

    endTime = clock();

    cout << "\nThe run time is " << static_cast<double>(endTime - startTime) / CLOCKS_PER_SEC
         << "s." << endl;
    return 0;
}

bool isPrime(int n)
{
    bool flag = true;
    for (int i = 2; i < n; i++)
    {

        if (n % i == 0)
            flag = false;
    }

    return flag;
}

运行截图

可以看到程序运行时间0.481s
在这里插入图片描述

c)代码

修改了判断素数的函数代码，并计算了程序运行时间。

思想：素数的因子只有1和它本身。如果数c不是素数，则还有其他因子。设a,b中定有一个大于sqrt( c ) ，一个小于sqrt( c ) 。所以m一定有一个小于等于其平方根的因数，那么验证素数时就只需要验证到其平方根就可以了。

#include <iostream>
#include <iomanip>
#include <cmath>
#include <ctime>
using namespace std;

bool isPrime(unsigned long);

int main()
{
    clock_t startTime, endTime;
    startTime = clock();

    int count = 0;
    for (unsigned long i = 2; i <= 10000; i++)
    {

        if (isPrime(i))
        {
            cout << setw(4) << i << "\t";
            count++;
            if (count != 0 && count % 10 == 0)
            {
                cout << endl;
            }
        }
    }
    endTime = clock();

    cout << "\nThe run time is " << static_cast<double>(endTime - startTime) / CLOCKS_PER_SEC
         << "s." << endl;
    return 0;
}

bool isPrime(unsigned long n)
{
    bool flag = true;
    unsigned long asquareRoot = static_cast<int>(sqrt(n)); // n的平方根
    for (int i = 2; i <= asquareRoot; i++)
    {
        if (n % i == 0)
            flag = false;
    }

    return flag;
}