第七周7.1数组运算课堂学习记录 求素数的方法改进/优化集锦《程序设计入门——C语言》第七期 浙江大学 翁恺
求素数基本方法及优化：
1.基本方法求素数：
从2到x-1测试是否可以整除，对于n来说要走n-1遍，n很大时相当于 n 遍。
#include<iostream>
using namespace std;
/*求素数基本方法*/
//从2到x-1测试是否可以整除，可以则非素数
//对于n来说要走n-1遍，n很大时相当于n遍
int isPrime(int x)
{
int ret = 1;
int i;
if (x == 1||x==0) { ret = 0; }
for (i = 2; i < x ; i++)
{
if (x%i == 0) {
ret = 0;
break;
}
}
return ret;
}
int main(){
int x;
scanf("%d", &x);
if (isPrime(x)) {
printf("%d是素数\n", x);
}
else {
printf("%d不是素数\n", x);
}
system("pause");
return 0;
}2.改进isPrime函数求素数：
去掉偶数(偶数一定不是素数)后，从3到x-1，每次加2。
如果x为偶数则立刻能判断，否则循环（n-3）/2遍，当n很大时相当于 n/2 遍。
完整程序（main函数未修改，只修改isPrime函数）：
#include<iostream>
using namespace std;
/*求素数改进方法1：
去掉偶数(偶数一定不是素数)后，从3到x-1，每次加2。
如果x为偶数则立刻能判断
否则循环（n-3）/2遍
当n很大时相当于 n/2 遍*/
int isPrime(int x)
{
int ret = 1;
int i;
if (x == 1 || x == 0 || (x % 2 == 0 && x != 2)) {
ret = 0;
}
for (i = 3; i < x ; i+=2)
{
if (x%i == 0) {
ret = 0;
break;
}
}
return ret;
}
int main(){
int x;
scanf("%d", &x);
if (isPrime(x)) {
printf("%d是素数\n", x);
}
else {
printf("%d不是素数\n", x);
}
system("pause");
return 0;
}3.进一步改进isPrime函数求素数：
去除偶数后从3遍历到√x即可。只需要循环约 √x/2 (sqrt(x)/2) 遍
数学原理：从素数的定义来看，“一个大于1的自然数，如果除了1和它自身外，不能被其他自然数整除的数。”
“因数”，我们要寻找的是除了自身与1没有因数的数字。而除了自身的平方根，因数都是成对存在的。而且这些因数对，一定是一大一小（除平方根外）。那么我们只要保留上面的遍历，但将遍历的终点设为所有因数对中较小值中的最大值（即平方根）就可以了。只要这个可以整除的值不存在，就说明该数字不存在因数对。那么自然也就是素数了。故而遍历只用到√x即可。
（注：原理转载自http://blog.sina.com.cn/s/blog_17b3f7fb60102x9wr.html）
#include<iostream>
#include<math.h>
using namespace std;
/*求素数改进方法2
去除偶数后从3遍历到√x即可
只需要循环 √x (sqrt(x)) 遍
*/
int isPrime(int x)
{
int ret = 1;
int i;
if (x == 1 || x == 0 || (x % 2 == 0 && x != 2)) {
ret = 0;
}
for (i = 3; i <= sqrt(x) ; i+=2)
{
if (x%i == 0) {
ret = 0;
break;
}
}
return ret;
}
int main(){
int x;
scanf("%d", &x);
if (isPrime(x)) {
printf("%d是素数\n", x);
}
else {
printf("%d不是素数\n", x);
}
system("pause");
return 0;
}4.求素数改进方法3：
判断是否能被已知的且<x的素数整除
只需要循环 比√x/2 更少的遍数——即 比x小的素数的个数 遍
#include<iostream>
using namespace std;
/*求素数改进方法3
判断是否能被已知的且<x的素数整除
只需要循环 比√x/2 更少的遍数
*/
//输入已知素数表和要判断的数x，判断x是否能被已知的且<x的素数整除
int isPrime(int x , int knownPrimes[] , int number0fKnowPrimes)
{
int ret = 1;
int i;
for (i = 0 ; i < number0fKnowPrimes; i++)
{
if (x % knownPrimes[i] == 0) {
ret = 0;
break;
}
}
return ret;
}
int main(){
const int number = 7; //输出前7个素数，可通过更改number改变想输出素数个数
int prime[number] = { 2 }; //素数数组中第一个素数为2
int count = 1; //素数数组中素数的个数
int i = 3; //从3开始判断是否为素数
/*调试用，输出表头
{
int i;
printf("\t\t");
for (i = 0; i < number; i++) {
printf("%d\t", i);
}
printf("\n");
}*/
while (count < number) {
//如果判断出i是素数的话，就把i加到prime数组中去
if (isPrime(i, prime, count)) {
prime[count++] = i; //此语句相当于：prime[count] = i; count++;
}
/*调试用，方便输出查看变量变化
{
printf("i=%d \tcnt=%d\t", i, count);
int i;
for (i = 0; i < number; i++) {
printf("%d\t", prime[i]);
}
printf("\n");
}*/
i++;
}
for (i = 0; i < number; i++) {
printf("%d", prime[i]);
if ((i + 1) % 10) printf("\t");
else printf("\n");
}
system("pause");
return 0;
}加上调试查看素数prime数组(前7个)的结果：
不加调试输出前100个素数运行结果：
5.求素数改进方法终极版：构造素数表（和前面的方法思路相反）
构造m以内的素数表步骤：
（1）令x为2
（2）将2x，3x，4x……直至nx<m的标记为非素数（将素数的整数倍数字都标记为非素数）
（3）令x为下一个没有被标记为非素数的数字，重复步骤（2），直到所有的数字都已经尝试完毕，素数表即构造完成。
比如：现在有15以内的数字表：
2 3 4 5 6 7 8 9 10 11 12 13 14 15
一开始全部标记为素数（红色），x = 2为素数，接着把2所有的倍数标记为非素数（黑色）之后变成：
2 3 4 5 6 7 8 9 10 11 12 13 14 15
然后令让x为下一个素数，即 x = 3 ，继续把3所有的倍数标记为非素数之后变成：
2 3 4 5 6 7 8 9 10 11 12 13 14 15
接着令让x为下一个素数，即 x = 5 ，继续把5所有的倍数标记为非素数之后变成：
2 3 4 5 6 7 8 9 10 11 12 13 14 15
接着令让x为下一个素数，即 x = 7 ……，直到 x = 13 之后，不再有素数，就停止了，最后得到的红色的就是素数，得到了15以内相应的素数表：
2 3 5 7 11 13
伪代码：
代码：
#include<iostream>
using namespace std;
/* 求素数改进方法——构造素数表
将素数的整数倍数字都标记为非素数
遍历剩余素数指导全部标记完为止 */
int main(){
const int maxNumber = 25; //打印25以内的素数
int isPrime[maxNumber];
int i;
int x;
//初始化isPrime数组素数标志均为1
for (i = 2; i < maxNumber; i++) {
isPrime[i] = 1;
}
for (x = 2; x < maxNumber; x++) {
//将素数的整数倍数字都标记为非素数
if (isPrime[x]) {
for (i = 2; i*x < maxNumber; i++) {
isPrime[i*x] = 0;
}
}
}
//打印最终没有被标记为非素数的素数们
for (i = 2; i < maxNumber; i++) {
if (isPrime[i]) {
printf("%d\t", i);
}
}
printf("\n");
system("pause");
return 0;
}输出结果：
测试查看算法标记非素数过程