PTA(BasicLevel)-1007素数对猜想

佚名 6年前 (2019-04-09) 随笔 1211人围观抢沙发百度已收录

一问题描述-素数对

　　让我们定义dn为：dn=pn+1−pn，其中pi是第i个素数。显然有d1=1，且对于n>1有dn是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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

　　 输入格式: 输入在一行给出正整数N。

　　 输出格式: 在一行中输出不超过N的满足猜想的素数对的个数。

　　 输入样例: 20

　　 输出样例: 4

二求解思路

　　求解出1到N范围内的素数，然后遍历此序列统计相邻素数差为2的素数对个数，重点在于判断素数的方法。

　　1. 素数就是一个只能被1和自己整除的正整数 - 枚举法　　　

　　　　只有1和它本身两个因数的自然数是素数，否则就叫合数。

def isPrime( N ):
    """ judge whether N is a prime number
    param:  N (int)
    retype: bool
    """
    if N <= 1:
        return False
    else:
        flag = True
　　　　　# from 2 to N-1
        for  i in range(2, N):
            if (N % i) == 0:
                flag = False
                break
        return flag

 
 2.数N如果不能被小于它的平方根√N整除，就是素数 - 开方判断素数法

　　　 假设N是一个合数，N = a*b,a为N的约数。a、b中肯定存在一个数>=根号N，另一个数<=根号N。
 只要<=根号N的数不能整除N,那么N就不存在除1外的因数。则N为素数。

import math
def isPrimeSqrt( N ):
    if N <= 1:
        return False
    else:
        flag = True
        num = int( math.sqrt(N) )
        for  i in range(2, num+1):
            if (N % i) == 0:
                flag = False
                break
        return flag

 
 3. - 埃氏素数筛法

三完整代码

　　python版本

import math def isPrimeSqrt( N ): if N <= 1: return False else: flag = True num = int( math.sqrt(N) ) for  i in range(2, num+1): if (N % i) == 0: flag = False break
        return flag def isPrime( N ): """ judge whether N is a prime number param: N (int) retype: bool """
    if N <= 1: return False else: flag = True for  i in range(2, N): if (N % i) == 0: flag = False break
        return flag def generatePrime( N ): prime = [ i for i in range(1,N+1) if isPrime(i) ] return prime N = int( input() ) cntPrimePair = 0 differ = 0 #for i in N:
primes = generatePrime( N ) length = len(primes) for i in range(length): if i < (length - 1): differ = primes[i+1] - primes[i] if differ == 2: cntPrimePair += 1
print(cntPrimePair)