C++ 素数的筛选法与穷举法

题目:素数大酬宾：

【问题描述】 某商场的仓库中有 n 种商品，每件商品按 1~n 依次编号。现在商场经理突发奇想，决定将编号为素数（质数）的所有商品拿出来搞优惠酬宾活动。请编程帮助仓库管理员将编号为素数的商品选出来。

【输入格式】 一行一个正整数 n，表示有 n 种商品，2≤n≤100000。

【输出格式】 一行若干个正整数，表示若干种商品编号且每个编号均为素数，请从小到大输出，每两个数之间有一个空格。

【输入样例】 20

【输出样例】 2 3 5 7 11 13 17 19

1、穷举法

穷举商品编号 2~n，判断每个编号是否为素数。这种方法效率不高，一旦 n 过大，程序就会超时。

#include<iostream>
#include<cmath>
using namespace std;
int main(){int n,i,j; bool flag;cin >> n;cout << 2;for(i = 3; i <= n; i++){flag = true;for(j = 2; j <= sqrt(i); j++)if(i % j == 0){flag = false;break;}if(flag) cout <<  " " << i;}cout << endl;return 0;
}

2、筛选法

筛选法的思路：

‌划去1‌：因为1不是素数。

‌圈出2‌：2是素数，留下2，划去2的倍数。

圈出3‌：3是素数，留下3，划去3的倍数。

‌圈出5‌：5是素数，留下5，划去5的倍数。

‌圈出7‌：7是素数，留下7，划去7的倍数。

‌重复上述步骤‌：继续用下一个未被划去的数作为除数，划去其倍数，直到没有更多的数可以划去为止。

#include<iostream>
#include<cmath>
using namespace std;
int main(){int n,i,j;bool p[100001];for(i = 0; i <= 100000; i++) p[i] = true;p[1] = false;cin >> n;cout << 2;  // 输出素数2// 思路:第一轮筛选2以及删除掉2的倍数；第二轮筛选3以及3的倍数...for(i = 2; i <= sqrt(n); i++)  if(p[i])  for(j = 2; i*j <= n; j++) p[i*j] = false;// 输出质数3包括3之后的素数for(i = 3; i <= n; i++)  if(p[i]) cout <<  " "<< i; cout << endl;return 0;
}