c++6级题之筛选法求质数

第1题 质数个数-一般做法程序填空时限1s空间256m题目描述输入n,输出1~n以内的质数的个数。n1000挖空的代码#includebits/stdc.husing namespace std;int main(){int n,s0;cinn;for(int i2;in;i) //质数是从2开始算{int flag1; //标记默认1表示是质数for(int j2;j*ji;j)if() //如果有因子flag0; //标记变成0if(flag) //标记没有变成0表示没有其他因子s; //表示是质数质数数量增加1}couts;return 0;}输入格式无输出格式无输入/输出例子1输入10输出4标签暂未设置关联标签知识点暂未设置关联知识点题解第1空i%j0第2题 质数个数-自定义函数程序填空时限1s空间256m题目描述输入n,输出1~n以内的质数的个数。n1000挖空的代码#includebits/stdc.husing namespace std;bool zs(int x) //判断是否质数的函数{for(int i2;i*ix;i)if()return false; //如果有因子就不是质数return true;}int main(){int n,s0;cinn;for(int i2;in;i)if()s;couts;return 0;}输入格式无输出格式无输入/输出例子1输入10输出4标签暂未设置关联标签知识点暂未设置关联知识点题解第1空x%i0第2空zs(i)1第3题 质数个数-筛选法程序填空时限1s空间256m题目描述输入n,输出1~n以内的质数的个数。n1000挖空的代码#includebits/stdc.husing namespace std;bool a[1002]; //数组数值为零默认都是素数int main(){int n,s0;cinn;for(int i2;i1000;i){if()//如果是素数for(int jii;j1000;) //将他的倍数记为合数a[j]i; //标记不为零表示不是素数}for(int i2;in;i)if(a[i]0) //如果是素数s;couts;return 0;}输入格式无输出格式无输入/输出例子1输入10输出4标签暂未设置关联标签知识点暂未设置关联知识点题解第1空a[i]0第2空ji第4题 质数个数-筛选法优化程序填空时限1s空间256m题目描述输入n,输出1~n以内的质数的个数。n1000挖空的代码#includebits/stdc.husing namespace std;bool a[1002];int main(){int n,s0;cinn;for(int i2;;i) // 去除不必要的计算{if(a[i]0)for(int jii;j1000;ji)a[j]i;}for(int i2;in;i)if(a[i]0)s;couts;return 0;}输入格式无输出格式无输入/输出例子1输入10输出4标签暂未设置关联标签知识点暂未设置关联知识点题解第1空in第5题 数学问题(noip2007mn)程序填空时限1s空间256m题目描述在一个渺无人烟的荒岛上待了XX年之后小z基本上啥都不会了。所以当小y告诉他任何一个大于等于4的偶数都能表示成两个质数的和这个事实的时候小z根本不相信小z现在想找出一些反例你能帮助他吗挖空的代码#include using namespace std; int n,x,k[1000005]; int date() { for(int i2;i1000000;i) //做素数表 k[i]1; for(int i2;i1000;i) for(int jii;j1000000;ji) k[j]0; } int main() { date(); cinn; for(int i1;in;i) { cinx; int flag1; for(int j2;jjx;j) //x的后一半已经在前一半那时试过不用重复 if( $#_%$ $#_%$) //两个加数都是质数就输出 { cout输入格式输入文件第一行为一个整数n1n50接下来有n行每行包含一个整数m。3m1000000输出格式输出文件共n行每行对应于每一个m如果m不能表示成两个质数的和则输出“NO WAY”否则输出一种方案。如果有多种可行方案输出两个质数的差最大的那一种。输入/输出例子1输入21011输出1037NO WAY!标签暂未设置关联标签知识点暂未设置关联知识点题解第1空k[j]1第2空k[x-j]1第6题 阶乘因子(yinzi) 查看测评数据信息桐桐刚刚学习了自然数N的阶乘N!被定义成从1到N的所有整数的乘积。例如5!5*4*3*2*1120随着数N的增大N!增长的非常快5!12010!3628800。桐桐想到了一种方法来列举那么大的数不是直接列出该数而是按照顺序列举出该数中各个质数因子出现的次数如825可描述为0 1 2 0 1意思是对825分解质因数这些质数因子中有0个21个32个50个71个11。请你编一个程序读入N值帮助桐桐按顺序输出N!所包含的质数因子的个数。输入格式只包含1个数N2N100000输出格式一个N!中所包含的质数因子的个数从最小的质数开始的序列数与数之间用一个空格隔开。输入/输出例子1输入53输出49 23 12 8 4 4 3 2 2 1 1 1 1 1 1 1样例解释无题解#includebits/stdc.husing namespace std;int n,a[1000005],s,t[1000005];const int N1e55;bool A[N];int main(){cinn;for(int i2;isqrt(n);i){if(A[i]0)for(int jii;jn;ji)A[j]1;}for(int i2;in;i){if(A[i]0)t[s]i;}for(int i2;in;i){if(A[i]0)a[i];else{int pi;for(int j1;js;j){while(p%t[j]0){pp/t[j];a[t[j]];}if(p1)break;}}}for(int i1;is;i){couta[t[i]] ;}return 0;}第7题 统计素数(pcount) 查看测评数据信息桐桐想统计某个区间范围里的素数例如A2B10则A和B之间包括A、B素数一共有4个分别为2357。现在桐桐给出N个区间范围问每个区间有多少个素数。请你帮助她统计一下。输入格式第一行一个整数 N(1N10^5)后有N行每行两个整数A B(1AB10^6)用空格隔开表示一个区间范围。输出格式共N行每行一个整数对应区间范围的素数个数。输入/输出例子1输入2 2 8 1 13输出46样例解释无题解#includebits/stdc.husing namespace std;const int N1e610;long long a[N],x,y,sum,n;bool ss(long long cs){long long b,s0;if(cs1){return 0;}for(int i2;i*ics;i){if(cs%i0){return 0;}}return 1;}void f(){for(int i1;i1e6;i){long long ans0;if(ss(i)) ans;a[i]a[i-1]ans;}}int main(){f();cinn;for(int i1;in;i){scanf(%d %d,x,y);printf(%d\n,a[y]-a[x-1]);}return 0;}第8题 单纯质因数(pprim)(nhoi2014小学甲组) 查看测评数据信息读五年级的楠楠刚学完了质数、合数、因数、质因数等概念。他还知道了每个合数都可以写成几个质数相乘的形式其中每个质数都是这个合数的因数叫做这个合数的质因数把一个合数用质因数相乘的形式表示出来叫做分解质因数聪明爱动脑筋的楠楠突然对具有互不相同的质因数的合数产生了兴趣。例如302*3*5它有互不相同的质因数702*5*7它也有互不相同的质因数。若一个合数中所有的质因数互不相同则把它称之为具有单纯质因数的合数。他想知道还有哪些数是单纯质因数的合数。你现在要帮楠楠解决的问题是已知N,依次输出N以内所有具有单纯质因数的合数。输入格式输入数据只一个整数N10N100000。输出格式依次输出N以内所有具有单纯质因数的合数。输入/输出例子1输入12输出6 10样例解释无题解#includebits/stdc.husing namespace std;int n,a[1000005],s,t[1000005],y,x;const int N1e55;bool A[N];int main(){cinn;for(int i2;isqrt(n);i){if(A[i]0)for(int jii;jn;ji)A[j]1;}for(int i2;in;i){if(A[i]0)t[s]i;}for(int i2;in;i){if(A[i]0){}else{int pi,l1;for(int j1;js;j){y0;while(p%t[j]0){pp/t[j];y;if(y1){l0;break;}}if(p1)break;if(l0)break;}if(l1){couti ;}}}return 0;}