首页 > 试题广场 >

素数对猜想 (20)

[编程题]素数对猜想 (20)

热度指数：3412 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

让我们定义 d_n 为：d_n = p_n+1 - p_n ，其中 p_i 是第i个素数。显然有 d₁ =1 且对于n&gt1有 d_n 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。

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

输入描述:

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

输出描述:

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

示例1

输入

输出

算法知识视频讲解

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)

Python

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)

Python

HelLeong-葉

用枚举暴力运行，但是Python效率太低，在PAT估计就跪了

from math import sqrt


def is_prime(n):
    """"判断所给数据是否为素数"""
    for num in range(2,  int(sqrt(n))+1):
        if n % num == 0:
            return False
    return True


def prime_list(n):
    """输出不大于所给数据内的所有素数"""
    lst = [2]
    for i in range(3, n+1, 2):
        if is_prime(i) == 1:
            lst.append(i)
    return lst


def count_num(lst):
    """"计算所给列表中有多少对相差为二的数对"""
    count = 0
    for i in range(len(lst)):
        if (lst[i] - lst[i-1]) == 2:
            count += 1
    return count


n = int(input())
prime_lst = prime_list(n)
print(count_num(prime_lst))

注意题目中的“不超过N”，是小于等于N

编辑于 2017-09-28 19:46:53 回复(0)