一 问题描述-素数对
让我们定义素数差dn为：dn=pn+1−pn，其中pi是第i个素数。显然有d1=1，且对于n>1有dn是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。
现给定任意正整数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.从给定的数字序列中不断剔除2到N的倍数，直到不变
普通地做法就是累次地剔除能被2到N之间的数整除的数，剩下的就是素数。实际上，可以将除数范围调整到2到根号N,在根号N之前已经把所有能被整除的数剔除了。
from math import sqrt
def seive( N ):
if N < 2:
return []
else:
L = [ i for i in range(2, N+1) ]
num = len(L)
for i in range(2, int( sqrt(num) )+1 ):
L = list( filter( lambda x: (x%i != 0) or x == i , L) )
return L
三 完整代码
python版本
import math
def generatePrime( N ):
prime = [ i for i in range(1,N+1) if isPrime(i) ]
return prime def sievePrime( n ):
""" Implement the seive og Eratosthenes
param: n (int)
retype: list(int)
"""
A = [ i for i in range(n+1)]
num = int( math.sqrt(n) )
for p in range(2, num+1):
if A[p] != 0: # p hasn't been eliminated on previous passes
j = p * p
while j <= n: # p*p <= n
A[j] = 0 # mark element as eliminated
j = j + p # 剔除p的倍数
L = [ item for item in A if item >= 2 ]
return L N = int( input() )
cntPrimePair = 0
differ = 0
#for i in N:
#primes = generatePrime( N )
primes = sievePrime( 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)
C语言版本
#include <stdio.h> int isPrime( int N )
{ /* 穷举法判断素数 */
if ( N <= ) {
return ;
} else {
int flag = ;
for ( i = ; i < N; i++ ) {
if ( (N % i) == ) {
flag = ;
break;
}
}
return flag;
}
} int isPrimeSqrt( int num )
{
int flag = ;
int N = sqrt(num);
int i;
for ( i = ; i <= N; i++ ){
if (num % i == ) {
flag = ;
}
}
return flag;
} int generatePrime( int primes[], int N )
{
int i, j;
for ( j = , i = ; i <= N; i++ ) {
if ( isPrimeSqrt(i) ) {
primes[j++] = i;
}
}
return j; /* prime index */
} int main(int argc, char *argv[])
{
int i, N, border;
int differ, cntPrimePair;
border = differ = cntPrimePair = ;
scanf("%d", &N); int primes[N];
for ( i = ; i < N; i++ ) {
primes[i] = ;
}
border = generatePrime( primes, N ); for ( i = ; i < (border-); i++ ) {
differ = primes[i+] - primes[i];
//printf("differ %d\n", differ);
if ( differ == ) {
cntPrimePair += ;
}
}
printf("%d\n", cntPrimePair); return ;
}