HDU - 3792- Twin Prime Conjecture【数论】题解

末蓝、 2021-07-24 17:10 368阅读 0赞

### 目录 ###

*   *   *  1.题目
         *  2.代码

### 1.题目 ###

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

### 2.代码 ###

#include<iostream>
    #include<cstdio>
    using namespace std;
    const int maxn=1e6+10;
    int a[maxn],prime[maxn];
    void isPrime()
    { 
      prime[1]=1;
      prime[0]=1;
      for(int i=2;i<maxn;i++)
      { 
         if(prime[i]==0)
    	 { 
    	 	 for(int j=i+i;j<maxn;j+=i)
    	 	  prime[j]=1;
    	 }	
      }	
    } 
    int main()
    {    
        isPrime();
        a[5]=1;///初值 
        for(int i=1;i<maxn;i++)
        { 
        	a[i+2]=a[i+1];  ///递推式 
        	if(prime[i]==0&&prime[i+2]==0)
        	  a[i+2]=a[i+1]+1;
    	}
    	int n;
    	while(cin>>n)
    	{ 
    		if(n<0)  break;
    		cout<<a[n]<<endl;
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，368人围观）

还没有评论，来说两句吧...

相关阅读

相关 UVA - 10394 - Twin Primes（素数对）

定义了一个素数对的概念，就是如果p是素数的话，p+2也是素数的话，那么（p，p+2）就是一组素数对；那么我们在打素数表的时候，顺便判断i-2是否是素数即可； i

电玩女神/ 2022年06月07日 00:23/ 0 赞/ 141 阅读

相关 HDU5104-Primes Problem

Primes Problem Problem Description Given a number n, please count how many tu

梦里梦外;/ 2022年06月03日 04:40/ 0 赞/ 187 阅读

相关 HDU 3988(数论)

问题描述: iSea is tired of writing the story of Harry Potter, so, lucky you, solving the fo

浅浅的花香味﹌/ 2022年05月31日 05:06/ 0 赞/ 159 阅读

相关 HDU - 4548 - 美素数【数论 + 打表】题解

目录 1.题目 2.代码 1.题目小明对数的研究比较热爱，一谈到数，脑子里就涌现出好多数的问题，今天，小明

柔光的暖阳◎/ 2021年07月25日 02:22/ 0 赞/ 403 阅读

相关 HDU - 5974 - A Simple Math Problem 【数论】题解

目录 1.题目 2.代码 1.题目 Given two positive integers a and b,

电玩女神/ 2021年07月25日 00:18/ 0 赞/ 343 阅读

相关 HDU - 2866- Special Prime【数论】题解

目录 1.题目 2.代码 1.题目 Give you a prime number p, if you co

傷城~/ 2021年07月25日 00:10/ 0 赞/ 368 阅读

相关 HDU - 2504- 又见GCD【数论+gcd 】题解

目录 1.题目 2.代码 1.题目有三个正整数a,b,c(0<a,b,c<10^6)，其中c不等于b。若a

逃离我推掉我的手/ 2021年07月25日 00:03/ 0 赞/ 362 阅读

相关 HDU - 3792- Twin Prime Conjecture【数论】题解

目录 1.题目 2.代码 1.题目 If we define dn as: dn = pn+1-pn, wh

末蓝、/ 2021年07月24日 17:10/ 0 赞/ 369 阅读

相关 HDU - 1576 - A/B 【数论+欧几里得】题解

目录 1.题目 2.代码 1.题目要求(A/B)%9973，但由于A很大，我们只给出n(n=A%9973)

逃离我推掉我的手/ 2021年07月24日 14:45/ 0 赞/ 311 阅读

相关 HDU - 1397 - Goldbach s Conjecture 【数论】题解

目录 1.题目 2.代码 1.题目 Goldbach’s Conjecture: For any even

偏执的太偏执、/ 2021年07月24日 12:11/ 0 赞/ 270 阅读