nyoj 题目孪生素数问题

孪生素数问题

时间限制：3000 ms | 内存限制：65535 KB

难度：3

描述: 写一个程序，找出给出素数范围内的所有孪生素数的组数。一般来说，孪生素数就是指两个素数距离为2，近的不能再近的相邻素数。有些童鞋一看到题就开始写程序，不仔细看题，咱们为了遏制一下读题不认真仔细的童鞋，规定，两个素数相邻为1的也成为孪生素数。

输入

第一行给出N(0<N<100)表示测试数据组数。
接下来组测试数据给出m，表示找出m之前的所有孪生素数。
(0<m<1000000)

输出

每组测试数据输出占一行，该行为m范围内所有孪生素数组数。

样例输入

1

14

样例输出

 #include <cstdio>

 #include <cstring>

 int prime[];

 int flag[];

 int ans[];

 int getPrime() {

     int cnt = ;

     for(int i = ; i <= ; i++) {

         if(flag[i] == ) {

             if(i !=  && i - prime[cnt-] <= ) {

                 ans[i] = ans[i-]+;

             }

             else {

                 ans[i] = ans[i-];

             }

             prime[cnt++] = i;

             for(int p = *i; p <= ; p+=i) {

                 flag[p] = ;

             }

         }

         else {

             ans[i] = ans[i-];

         }

     }

     return cnt;

 }

 int main(int argc, char const *argv[])

 {

     memset(flag, , sizeof(flag));

     int n;

     scanf("%d",&n);

     ans[] = ;

     int cnt = getPrime();

     while(n--) {

         int m;

         scanf("%d",&m);

         printf("%d\n",ans[m]);

     }

     return ;

 }

巴特西

nyoj 题目孪生素数问题

孪生素数问题

最新文章

热门文章

巴特西

nyoj 题目 孪生素数问题

孪生素数问题

最新文章

热门文章

nyoj 题目孪生素数问题