#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int fun1(int n, int ans[]) {
int len=0;
int flag=0;
for(int i=2; i<=n; i++) {
printf("i = %3d ", i);
for(int j=2; j<=sqrt(i); j++) {
if(i%j==0) {
flag=1;
break;
}
}
printf("flag = %d\n", flag);
if(!flag) {
ans[len++]=i;
printf("ans[%d] = %3d\n", len-1, ans[len-1]);
} else {
flag=0;
}
}
printf("len = %d\n",len-1);
return len;
}
int fun2(int n, int ans[]) {
int a[n+1]= {0};
int len=0;
for(int i=2; i<=n; i++) {
if(!a[i]) {
ans[len++]=i;
printf("ans[%3d] = %3d\n", len-1, ans[len-1]);
for(int j=1, k=i*j; k<=n; j++) {
a[k]=1;
k=i*j;
}
}
}
return len;
}
int main() {
int n = 0;
n = 100;
int ans1[n], ans2[n];
int len1=fun1(n, ans1);
printf("\n--------------------------------------\n");
int len2=fun2(n, ans2);
printf("len1 = %d\n", len1);
printf("len2 = %d\n", len2);
for(int i=0; i<len1; i++) {
printf("%-3d", ans1[i]);
}
puts("");
for(int i=0; i<len2; i++) {
printf("%-3d", ans2[i]);
}
return 0;
}
对 f2() 的修改
f3( )
线性筛
https://www.luogu.com.cn/problem/P3383
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
void f3(int n,int a[]) {
int b[n+1];
memset(b,0,sizeof(b));
int index=0;
for(int i=2;i<=n;i++) {
if(!b[i]) a[index++]=i;
for(int j=0;i*a[j]<=n&&j<index;j++) {
b[i*a[j]]=1;
if(i%a[j]==0) break;
}
}
}
int main() {
int n,q;
int index;
while(~scanf("%d%d",&n,&q)) {
int a[n];
f3(n,a);
while(q--) {
scanf("%d",&index);
printf("%d\n",a[index-1]);
}
}
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)