hdu3792 Twin Prime Conjecture(树状数组+线性筛)

xiaoxiao2021-02-28  74

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3792点击打开链接

Twin Prime Conjecture

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3417    Accepted Submission(s): 1257 Problem Description If we define dn as: dn = pn+1-pn, where pi is the i-th prime. It is easy to see that d1 = 1 and dn=even for n>1. Twin Prime Conjecture states that "There are infinite consecutive primes differing by 2". Now given any positive integer N (< 10^5), you are supposed to count the number of twin primes which are no greater than N.   Input Your program must read test cases from standard input. The input file consists of several test cases. Each case occupies a line which contains one integer N. The input is finished by a negative N.   Output For each test case, your program must output to standard output. Print in one line the number of twin primes which are no greater than N.   Sample Input 1 5 20 -2   Sample Output 0 1 4   题意:让你计算0~n里面相差2的素数有几个 记忆化 树状数组 线性筛素数

#include <stdio.h> #include <stdlib.h> #include <iostream> #include<algorithm> #include <math.h> #include <string.h> #include <limits.h> #include <string> #include <queue> #include <stack> using namespace std; int su[1111111]; int ans[111111]; int c[111111]; int lowbit(int x) {return x&(-x);} void add(int k,int num) { while(k<100000) { c[k]+=num; k+=lowbit(k); } } int read(int k) { int s=0; while(k>0) { s+=c[k]; k-=lowbit(k); } return s; } int main() { for(int i=2;i<=100000;i++) { if(su[i]==0) { for(int j=i;j<=100000;j+=i) { if(j!=i) su[j]=1; } } } su[0]=su[1]=1; for(int i=1;i<=100000;i++) { if(su[i]==0&&su[i-2]==0) add(i,1); ans[i]=read(i); } int n=0; while(scanf("%d",&n)&&n>=0) printf("%d\n",ans[n]); }

转载请注明原文地址: https://www.6miu.com/read-78036.html

最新回复(0)