5 条题解
-
0
#include<stdio.h> const int N=1e6+5; int box[N]; void primes() { box[0]=box[1]=1; for(int i=2;i<N;i++) { if(!box[i]) { for(int j=2;j*i<N;j++) { box[j*i]=1; } } } } int main() { primes(); int n; scanf("%d",&n); while(n--) { int count=0; int m; scanf("%d",&m); for(int i=1;i<=m;i++) { for(int j=i+1;j<i+3;j++) { if(j>m) break; if(!box[i]&&!box[j]) { // printf("%d %d",i,j); count++; } } } printf("%d\n",count); } }
-
0
#include<stdio.h> int box[1000000+5]; const int N=1e6+5; void primes(){ box[0]=1; box[1]=1; for(int i=2;i<=N;i++){ if(box[i]==0){ for(long long j=i;j*i<=N;j++){ box[i*j]=1; } } } } int main() { int n; scanf("%d",&n); primes(); while(n--){ int m; scanf("%d",&m); int cnt=0; for(int i=2;i<=m;i++){ if((box[i]==0&&box[i-2]==0)||(box[i]==0&&box[i-1]==0)){ cnt++; } } printf("%d\n",cnt); } return 0; }
-
0
刚学的热乎的素数筛 ```#include<stdio.h> #include<math.h> const int n=1e6+5; int box[1000000]; void primes(); int main() { int t; scanf("%d",&t); primes(); box[0]=1; box[1]=1; while(t--) { int cnt=0; int m; scanf("%d",&m); for(int i=2;i<=m;i++) { if((box[i]==0&&box[i-1]==0)||(box[i]==0&&box[i-2]==0)) { cnt++; } } printf("%d\n",cnt); } } void primes() { for(int i=2;i<=n;i++) { if(box[i]==0) { for(int j=i+i;j<=n;j+=i) { box[j]=1; } } } } `````` `````````
-
0
素数筛选法: 开一个大数组,下标表示所有1 -- m之间的数。思路是把素数标记为1, 非素数标记为0; 因为偶数肯定不是素数,所以先标记所有偶数为0;还有一种方法是让下标从3开始,每次加2,就避过了偶数, 这样不用管偶数,更加省时。然后就是从3到根号下m之间,只要是素数,它的倍数肯定不是素数,标记为0. 这样,剩下的被标记为1的奇数就是要找的1 -- m之间的所有素数。 另外,总共进行n次测试,在测试之前标记完成,每次测试只要取其结果即可。
int func(int); int main(void) { int n, m, i, j, num; int buf[100000]={0};//注意buf树状数组 scanf("%d", &n); j=0; buf[j++]=2; /*把2到1000000的素数放到数组里*/ for(i=3; i<1000001; i += 2){ if(func(i) == 1){ buf[j++] = i; } } while(n--){ num=0; scanf("%d", &m); for(i=1; i<=m; i++){ if(buf[i]>m){ break; } if((buf[i]-buf[i-1] == 1) || (buf[i]-buf[i-1] == 2)){ num++; } } printf("%d\n", num); } return 0; } /*求是否为素数*/ int func(int n) { if(n<2){ return -1; } int i; for(i=2; i<=sqrt(n); i++){ if(n%i==0){ return 0; } } return 1; }
-
0
一次性统计完所有数字对应的孪生素数对数,这样就不需要每次重新循环统计。
#include <cstdio> const int MAXN = 1000010; bool isPrime[MAXN]; int twinPrimes[MAXN]; int fillIsPrime(){ for(int i = 2; i <= MAXN; i++){ isPrime[i] = true; } for(int i = 2; i <= MAXN; i++){ if(isPrime[i]){ for(int j = 2 * i; j <= MAXN; j += i){ isPrime[j] = false; } } } return 0; } int main(){ fillIsPrime(); int n, m, rec = 1; scanf("%d", &n); twinPrimes[0] = 0; twinPrimes[1] = 0; twinPrimes[2] = 0; for(int i = 3; i <= 1000010; i ++){ if(isPrime[i] && isPrime[i - 2]){ rec ++; } twinPrimes[i] = rec; } for(int i = 1; i <= n; i ++){ scanf("%d", &m); printf("%d\n", twinPrimes[m]); } return 0; }
- 1
信息
- ID
- 128
- 时间
- 3000ms
- 内存
- 128MiB
- 难度
- 8
- 标签
- (无)
- 递交数
- 1353
- 已通过
- 185
- 上传者