求小于n的孪生素数的个数，求和用树状数组
1 #include <iostream>
2 #include <stdio.h>
3 #include <string.h>
4 using namespace std;
5
6 const int maxx=100000;
7
8 #define lowbit(i) (i&(-i))
9
10 bool prime[maxx+10];
11 int tree[maxx+10];
12 void add(int i,int val)
13 {
14 while(i<=maxx)
15 {
16 tree[i]+=val;
17 i+=lowbit(i);
18 }
19 }
20
21 int sum(int i)
22 {
23 int s=0;
24 while(i>0)
25 {
26 s+=tree[i];
27 i-=lowbit(i);
28 }
29 return s;
30 }
31 void getprime()
32 {
33 int i,j;
34 memset(prime,1,sizeof(prime));
35 prime[0]=prime[1]=0;
36 for(i=2;i*i<maxx;i++)
37 {
38 if(prime[i])
39 for(j=i*i;j<=maxx;j+=i)
40 prime[j]=0;
41
42 }
43 for(j=2;j<=maxx;j++)
44 if(prime[j] && prime[j-2]) {add(j,1);}
45
46 }
47
48 int main()
49 {
50 getprime();
51 int x;
52 freopen("in.txt","r",stdin);
53 while(scanf("%d",&x)!=EOF)
54 {
55 if(x<0) break;
56 printf("%d\n",sum(x));
57
58 }
59 return 0;
60 }