首页 > ACM题库 > HDU-杭电 > HDU 3792-Twin Prime Conjecture[解题报告]HOJ
2015
04-13

HDU 3792-Twin Prime Conjecture[解题报告]HOJ

Twin Prime Conjecture

问题描述 :

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.

输入:

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.

输出:

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.

样例输入:

1
5
20
-2

样例输出:

0
1
4

#include <stdio.h>
#include <math.h>
int a[10000]={2},num[100000]={0,0};
int main()
{
    int n,i,j,g,temp;
    for(g=0,i=3;i<100000;i++)
    {
        temp=sqrt(i);
        for(j=2;j<=temp;j++)
            if(i%j==0)break;
        if(j>temp)
        {
            a[g]=i;
            num[i]=num[i-1]+(a[g-1]+2==a[g]?1:0);
            g++;
        }
        else
            num[i]=num[i-1];
    }
    while(scanf("%d",&n)&&n>=0)
    {
        printf("%d\n",num[n]);
    }
    return 0;
}

  1. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!

  2. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?

  3. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.