网站开发前景,专业网站设计制作改版,哈尔滨市建筑信息网,软件开发包含哪些内容题目
(素数)素数是只能被1和自已整除的整数。例如,235和7是素数而468和9不是素数 a)编写一个函数#xff0c;确定一个数是否是素数。 b)在程序中使用这个函数#xff0c;该程序确定和打印2 ~10000之间的所有素数。在确信已找到所有的素数之前#xff0c;实际需测试这些数中…题目
(素数)素数是只能被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_castdouble(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_castdouble(endTime - startTime) / CLOCKS_PER_SEC s. endl;return 0;
}bool isPrime(unsigned long n)
{bool flag true;unsigned long asquareRoot static_castint(sqrt(n)); // n的平方根for (int i 2; i asquareRoot; i){if (n % i 0)flag false;}return flag;
}运行截图
代码运行时间0.19s比b)中代码快了不少
