首页 > 试题广场 >

素数对猜想 (20)

[编程题]素数对猜想 (20)
  • 热度指数：3432 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
让我们定义 dn 为：dn = pn+1 - pn ，其中 pi 是第i个素数。显然有 d1 =1 且对于n&gt1有 dn 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。

现给定任意正整数N (< 105 )，请计算不超过N的满足猜想的素数对的个数。

输入描述:
每个测试输入包含1个测试用例，给出正整数N。


输出描述:
每个测试用例的输出占一行，不超过N的满足猜想的素数对的个数。
示例1

输入

20

输出

4
算法知识视频讲解
添加回答
C/C++
Myhui头像 Myhui 
#include <iostream>
using namespace std;
bool isprime(int n){
    if(n<=1) return false;
    for(int i=2;i*i<=n;i++)
        if(n%i==0) return false;
    return true;
}
int main(){
    int n,sum=0,lastprime=2;
    cin>>n;
    for(int i=1;i<=n;i++){
        if(isprime(i)){
            if(i-lastprime==2) sum++;
            lastprime=i;
        }
    }
    cout<<sum;
    return 0;
}

发表于 2018-02-19 18:10:36 回复(0)
啥头像 啥
感觉这种情况用筛选法要简单明了： 
N = input()
prime = [True]*(N+1)
for i in range(2, N/2+1):
    s = i+i
    while s<=N:
        prime[s] = False
        s += i
cnt = 0
for i in range(5, N+1):
    if prime[i] and prime[i-2]:
        cnt += 1
print(cnt)


发表于 2016-01-17 21:01:12 回复(0)
想按时下班的我拥抱太阳头像 想按时下班的我拥抱太阳 
#include <stdio.h>
#include <math.h>
int main(){
	int N;
	scanf("%d",&N);
	int i=0,j=0,w=0,count=0;
	int gen;
	int a[N]; 
	a[w]=2;
	w++;
	a[w]=3;
	w++;
	//判断是不是素数 
	for(i=5;i<=N;i+=2){//i要判断的这个数 
		gen=sqrt(i);
		for(j=2;j<=gen;j++){
			if(i%j==0){
				break;
			}
			if(j==gen){
				a[w]=i;
				w++;
			}
		}
		
	}
	//判断相邻的两个素数是不是相差2 
	for(i=1;i<w;i++){
		if(a[i]-a[i-1]==2){
			count++;
		}
	}
	printf("%d",count);
	
	return 0;
}

发表于 2016-08-25 15:02:30 回复(0)
C/C++
巴也战无不胜头像 巴也战无不胜 
#include <stdio.h>
int main()
{
    int N,i,j,last;
    int count;
    _Bool flag[100001] = {0};
    while(scanf("%d",&N) == 1)
    {
        count = 0;
        last = 2;
        for(i = 2;i <= N;i++)
        {
            if(flag[i] == 0)
            {
                if(i - last == 2 && i != 2)
                    count++;
                last = i;
                for(j = i + i;j <= N;j +=i)
                    flag[j] = 1;
            }
        }
        printf("%d\n",count);
    }
}

发表于 2021-02-17 20:46:43 回复(0)
C/C++
猫猫猫1头像 猫猫猫1 
#include<bits/stdc++.h>
using namespace std;

bool isprime(int n){
	int m=sqrt(n*1.0);
	for(int i=2;i<=m;i++){
		if(n%i==0){
			return 0;
		}
	}
	return 1;
}

int main() {
    ios::sync_with_stdio(0);
	int n,count=0;
	cin>>n;
	for(int i=2; i+2<=n; i++) {
		if(i%2==1&&isprime(i)&&isprime(i+2)) {
			count++;
		}
	}
	cout<<count<<endl;
	return 0;
}

发表于 2022-11-15 10:05:15 回复(1)
hestyle头像 hestyle


这道题其实也不难，关键的切入点是如何快速寻找素数。
最容易想到的就是穷举法，一一判断[1, n]中的每一个数i是否是素数，然后判断i + 2是否是素数。

不过经常刷题的一般都知道有一种快速求某段区间中的所有素数方法——筛选法。算法核心思想如下：
假设让你找出[1,1000]中的所有素数，你先初始化[2, 1000]中的数都是素数。然后开始遍历[2, 1000]区间

当n = 2时，是素数（这个是特殊起始值），
    把2的倍数4、6、8、...、1000 全被设为非素数，因为2是这些数的因子
当n = 3时，是素数（n < 3时没能筛除掉它，默认是素数，实际上它也是素数），
    把3的倍数6、9、12、...、999全部设为非素数，因为3是这些数的因子
当n = 4时，早就被n = 2时筛除了。。。
当n = 5时，是素数（n < 5时没能筛除掉它，默认是素数，实际上它也是素数），
    把5的倍数10、15、20、...、1000全部设为非素数，因为3是这些数的因子
....
当n = 1000时，找就n = 2筛除掉了。。。

最终没有被筛除掉2、3、5、...的就是素数.

#include <iostream>
(720)#include <cstring>
using namespace std;

int main() {
    int n = 0, count = 0, tempNum;
    //primerTable[i]记录i是否是素数,记得初始化0、1不是素数
    bool primerTable[100001] = {false, false};
    while (scanf("%d", &n) != EOF) {
        count = 0;
        //初始化[2, 100000]所有都是素数
        memset(primerTable + 2, 1, 100001);
        //使用筛选法，找出[2, 100000]中的所有素数
        for (int i = 2; i < 100001 && i <= n; ++i) {
            if (primerTable[i]) {
                //将i的倍数全设置为非素数（筛选法的核心）
                tempNum = i * 2;
                while (tempNum < 100001 && tempNum <= n) {
                    primerTable[tempNum] = false;
                    tempNum += i;
                }
                //现在i确定是素数了，如果i - 2也是素数，不就符合条件了么
                if (primerTable[i - 2]) {
                    count += 1;
                }
            }
        }
        printf("%d\n", count);
    }
    return 0;
}
————————————————
版权声明：本文为CSDN博主「hestyle」的原创文章，遵循 CC 4.0 BY 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://hestyle.blog.csdn.net/article/details/104760158
发表于 2020-03-09 20:32:17 回复(0)
C/C++
不偷不抢安度因_头像 不偷不抢安度因_ 
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
#define MAX 100000
 
int is_prime(int);
 
 
 
int main()
{
    int prime[MAX/2] = {2, 3, 5};
    int n;
    int count = 0;
    for(int j = 2; j <= MAX; j++)
    {
        if(is_prime(j))
        {
            prime[count++] = j;
            //printf("%d ", j);
        }
    }
    while(~scanf("%d", &n))
    {
        int i = 1;
        int result = 0;
        while(prime[i] <= n)
        {
            if((prime[i] - prime[i-1]) == 2)
                result++;
            i++;
        }
        printf("%d\n", result);
 
    }
    return 0;
}
 
int is_prime(int n)
{
    int s = sqrt(n);
    for(int i = 2; i <= s; i++)
    {
        if(n % i == 0)
            return 0;//不是素数
    }
    return 1;//是素数
}

编辑于 2020-03-04 20:56:00 回复(0)
奋斗201906192227359头像 奋斗201906192227359 
import java.util.ArrayList;
import java.util.Scanner;
 
public class Main
{
    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();
        ArrayList<Integer> primeList = new ArrayList<>();
        for (int i = 2; i < num; i++)
            if (isPrime(i))
                primeList.add(i);
        int cnt = 0;
        for (int i = 0; i < primeList.size() - 1; i++)
            if (primeList.get(i + 1) - primeList.get(i) == 2)
                cnt++;
        System.out.print(cnt);
    }
 
    public static boolean isPrime(int n)
    {
        int q = (int) Math.sqrt(n);
        for (int i = 2; i <= q; i++)
            if (n % i == 0)
                return false;
        return true;
    }
}

发表于 2020-02-19 13:42:54 回复(0)
Python
长风与你头像 长风与你 
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2019/8/10 17:58
# @Author  : suxiaorui

num = input()
num = int(num)
prime_list = []
# 双重循环寻找不超过num的素数添加到列表里
for i in range(2,num+1):
    for j in range(2,int(pow(i,0.5))+1):
        if i % j == 0:
            break
    else:
        prime_list.append(i)
sum = 0
# 遍历素数列表寻找符合相邻相差为1的素数对。
for i in range(0,len(prime_list)-1):
    if prime_list[i+1] - prime_list[i] == 2:
       sum = sum + 1
print(sum)

发表于 2019-08-10 20:43:08 回复(0)
Xechos头像 Xechos
#include<iostream>
using namespace std;
int a[100000]={0};
int main() {
    int count=0;
    long n;
    for(int i=2;i<50001;i++) {
        for(int j=2;i*j<100000;j++) {
            if(a[i*j]==0) {
                a[i*j]=1;
            }
        }
    }
    cin>>n;
    for(int i=2;i<=n-2;i++) {
        if(a[i]==0&&a[i+2]==0) {
            count++;
        }
    }
    cout<<count<<endl;
    return 0;
} 
发表于 2019-08-07 13:47:09 回复(0)
书灏头像 书灏 
#include <iostream>
#include <cmath>
using namespace std;

int main(int argc, const char * argv[]) {
    int n,i,count=0,arr[100000],k = 0;
    cin>>n;
    if (n==1||n==2||n==3||n==4) {
        cout<<0<<endl;
    }
    else{
    for (i=2; i<=n; i++) {
        int flag=1;
        for (int j=2; j<=sqrt(i); j++) {
            if (i%j==0) {
                flag=0;
                break;
            }
        }
        if (flag) {
            arr[k++]=i;
        }
        
    }
    for (int q=0; q<k; q++) {
        if (arr[q+1]-arr[q]==2) {
            count++;
        }
    }
    cout<<count<<endl;
    }
    return 0;
}


	


最暴力，数组开大一点啊！不然就个点过不了！

发表于 2019-06-10 17:45:59 回复(0)
不知道做算法还是做py的喜茶头像 不知道做算法还是做py的喜茶
暴力解决，都用for 
import java.util.Scanner; public class Code1039 { public static void main(String[] args) {
        Scanner sc=new Scanner(System.in); int data=sc.nextInt(); int j; boolean flag; int temp=0; int[] sushi=new int[data]; for(int i=2;i<data;i++){
            flag=false; for(j=2;j<i/2;j++){ if (i%j==0){
                    flag=true; break;
                }
            } if (flag==false){
                temp++;
                sushi[temp]=i; //System.out.println(i);  }
        } int count=0; for (int i=0;i<sushi.length-1;i++){ int a=sushi[i+1]; int b=sushi[i]; if (a-b==2){
                count++;
            }
        }
        System.out.println(count);
    }
}

发表于 2019-05-12 20:36:58 回复(0)
忘川201806190945464头像 忘川201806190945464 
#include <iostream>
#include <vector>
using namespace std;

bool check(unsigned a) {
    for (int i = 2; i*i <= a; ++i)
        if (a%i == 0)
            return false;
    return true;
}
int main() {
    //筛出从1~n的素数，存入p[n]
    //建立dn=p[n+1]-p[n],如果dn==2,++count;

    //或制造一个bool判断素数的函数
    //从3~n，看看是否满足俩个都是素数，如果是则count+1;
    unsigned n; cin >> n;
    unsigned count=0;
    for(unsigned i=5;i<=n;++i)
        if (check(i) && check(i-2))
            ++count;
    cout << count;
    return 0;
}

发表于 2019-04-02 17:26:45 回复(0)
Python
11122222222222222222头像 11122222222222222222
长了点，素数那里我会尽量想办法优化的，应该可以尝试用数组来获取下一个有效的素数
n=int(raw_input())
def is_prime(N):
    return N>1 and all(N%d for d in range(2,int(N**.5)+1))
prime,p=[1]*(n+1),[]
prime[0]=prime[1]=0
for i in range(2,n+1):
    if is_prime(i):
        j=2*i
        while j<=n:
            prime[j]=0
            j+=i
for i,val in enumerate(prime):
    if val:
        p.append(i)
print sum(j-i==2 for i,j in zip(p,p[1:]))
发表于 2019-01-11 11:21:56 回复(0)
MniQ头像 MniQ
#include<iostream> 
#include<cstdlib>

using namespace std;

//1007 素数对猜想
//输入n<10^5
//注意本题另外定义IsPrime()的话怎么写都会超时
//只能用筛数法

/*
**用不到
**
bool IsPrime(unsigned int n) {
    if (n < 2)
        return false;
    if (n == 2) 
        return true;
    if (n % 2 == 0)
        return false;
    for (int i = 3; i < n; i++) {
        if (n % i == 0)    return false;
    }
    return true;
}
*/

int main() {
    unsigned int n;
    unsigned int notPri[100000]={};
    
    cin >> n;
    

    //筛数法
    notPri[0]=1;
    notPri[1]=1;
    for(unsigned int i=2;i<n;i++){
        if(!notPri[i]){
            for(int j=2*i;j<=n;j+=i) notPri[j]=1; //注意是小于等于
        }
    }//筛数完毕
    
    
    int cnt = 0;
    int lastprime = 2; 
    for (unsigned int i = 3; i<=n; i++) { //注意是小于等于，只写小于pat有一个测试点不通过
        if(!notPri[i]){
            if(i-lastprime==2) cnt++;
            lastprime=i;
        }
    }
    cout << cnt;


    return 0;
}


编辑于 2018-12-31 13:51:29 回复(2)
绕骨酥情头像 绕骨酥情 



	#include <iostream>





	#define N 100000





	using namespace std;





	int main()
{
    int n ;
    cin>>n ;





	    int a[N] , s=1 ;
    a[0] = 2 ;
    int k=1 ;
    int num=0 ;
    for( int i=2 ; i<n ; ++i )
    {
        for( int j=1 ; j<i ;++j )
        {
            if( i%j==0 )
                s=j ;
        }
        if( s==1 )
        {
            a[k] = i ;
            ++k ;
        }
    }
    for( int m=0 ; m<k ; ++m )
    {
        if( a[m+1]-a[m]==2 )
        {
            ++num ;
        }
    }





	    cout <<num<<endl ;
    return 0;
}


//求指教，这个不是满分，有超时问题，请问怎么优化

发表于 2018-12-04 22:01:42 回复(1)
Disconnect头像 Disconnect 
def isp(a):
    for j in range(2,int(pow(a,0.5)+1)):
        if a%j==0:
            return False
    return True

n = input()
n = int(n)
con,cu = [],0
for i in range(2,n+1):
    if isp(i):
        con.append(i)
for i in range(0,len(con)-1):
    if con[i+1]-con[i]==2:
        cu+=1
print(cu)

发表于 2018-12-02 10:27:58 回复(0)
C/C++
BlackCarDriver头像 BlackCarDriver
#include<iostream>
#include<string.h>
#include<string>
#include<vector>
using namespace std;
const int maxn = 100990;
int not_prime[maxn];
vector<int>prime;
vector<int>ans; 
void fun(){
    memset(not_prime,-1,sizeof(not_prime));
    not_prime[0] = not_prime[1]=1;
    for(int i=2;i<maxn;i++){
        if(not_prime[i]==1) continue;
        prime.push_back(i);
        for(int j=i+i;j<maxn;j+=i) not_prime[j]=1;
    }
return;
}
int main() {
    fun();
    for(int i=0;i<prime.size()-1;i++){
        if(prime[i+1]-prime[i]==2)ans.push_back(prime[i]);
    } 
    vector<int>::iterator it;
    int n;
    cin>>n;
    it = ans.begin();
    while(*it<=n) it++;
    cout<<it-ans.begin()<<endl;
}
发表于 2018-11-29 16:51:22 回复(0)
SupritYoung头像 SupritYoung
详细题解
发表于 2018-11-24 11:25:40 回复(0)
C/C++
Caffeine头像 Caffeine 
思路分成三个函数。

i < (int)(v.size()-1)

注意 vector的size函数返回的是unsigned int

#include <iostream>

#include <vector>

#include <math.h>

using namespace std;





bool IsPrime(int n)

{

    if (n == 2)

        return false;

    for (int i = 2; i < sqrt(n) + 1; i++)

    {

        if (n%i == 0)

        {

            return false;

        }

    }

    return true;

}



void PrimeList(vector<int> &v, int n)

{

    for (int i = 2; i <= n; i++)

    {

        if (IsPrime(i) == true)

            v.push_back(i);

    }

}





int CountPrime(int n)

{

    vector<int> v;

    PrimeList(v, n);

    int count = 0;

    for (int i = 0; i < (int)(v.size()-1); i++)

    {

        if (v[i + 1] - v[i] == 2)

        {

            count++;

        }

    }

    return count;

}



int main()

{

    int n;

    while (cin >> n)

    {

        cout << CountPrime(n) << endl;

    }



}

发表于 2018-08-14 09:41:38 回复(0)
提交观点

问题信息

难度：
38条回答 12839浏览

热门推荐

通过挑战的用户

相关试题

素数对猜想 (20)

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号