//线性筛法-找质数以及每个数的最小质因数 #include<iostream> using namespace std; const int N=1e5+10; int n,p[N],minp[N]; //p[N]存质数 minp[N]存每个数的最小质因子 int cnt; bool st[N]; void get_p(int n) { for(int i=2;i<=n;i++) { if(!st[i]) { // st[i]=true; minp[i]=i; //质数i的最小质因子是本身 p[cnt++]=i; //存质数 } for(int j=0;p[j]*i<=n;j++) { st[p[j]*i]=true; //标记每个合数 minp[p[j]*i]=p[j]; //此循环中每个合数的最小质因子都是p[j] if(i%p[j]==0) break; } } } int main(void) { cin>>n; get_p(n); for(int i=0;i<cnt;i++) cout<<p[i]<<' '; cout<<endl; for(int i=1;i<=n;i++) cout<<minp[i]<<' '; return 0; }
0.0分
0 人评分
C语言训练-素数问题 (C语言代码)浏览:998 |
2003年秋浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:605 |
C语言训练-大、小写问题 (C语言代码)浏览:614 |
简单的a+b (C语言代码)浏览:817 |
C语言程序设计教程(第三版)课后习题3.7 (C语言代码)浏览:569 |
C语言程序设计教程(第三版)课后习题10.1 (C语言代码)浏览:567 |
图形输出 (C语言代码)浏览:1387 |
1050题解(结构体数组与结构体指针的使用)浏览:1111 |
简单的a+b (C语言代码)浏览:631 |
1197求助浏览:631 |