英文网站建设深圳,餐厅网页设计模板html代码,wordpress网站工具栏,虚拟网站官网题目:素数大酬宾#xff1a;
【问题描述】 某商场的仓库中有 n 种商品#xff0c;每件商品按 1~n 依次编号。现在商场经理突发奇想#xff0c;决定将编号为素数#xff08;质数#xff09;的所有商品拿出来搞优惠酬宾活动。请编程帮助仓库管理员将编号为素数的商品选出来…题目:素数大酬宾
【问题描述】 某商场的仓库中有 n 种商品每件商品按 1~n 依次编号。现在商场经理突发奇想决定将编号为素数质数的所有商品拿出来搞优惠酬宾活动。请编程帮助仓库管理员将编号为素数的商品选出来。
【输入格式】 一行一个正整数 n表示有 n 种商品2≤n≤100000。
【输出格式】 一行若干个正整数表示若干种商品编号且每个编号均为素数请从小到大输出每两个数之间有一个空格。
【输入样例】 20
【输出样例】 2 3 5 7 11 13 17 19
1、穷举法
穷举商品编号 2~n判断每个编号是否为素数。这种方法效率不高一旦 n 过大程序就会超时。
#includeiostream
#includecmath
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不是素数。 圈出22是素数留下2划去2的倍数。 圈出33是素数留下3划去3的倍数。 圈出55是素数留下5划去5的倍数。 圈出77是素数留下7划去7的倍数。 重复上述步骤继续用下一个未被划去的数作为除数划去其倍数直到没有更多的数可以划去为止。 #includeiostream
#includecmath
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;
}
