本文主要是介绍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;
}
运行截图
代码运行时间0.19s,比b)中代码快了不少!
这篇关于C++大学教程(第九版)6.29素数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!