如果一个合数x=p⋅q,p,q是素数且p≠q,我们称x是双素数。 现给你一个区间[a,b],求区间内的的双素数个数。
时间: 2024-05-29 12:12:37 浏览: 16
首先需要一个判断素数的函数,可以使用试除法:
def is_prime(n):
if n < 2:
return False
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return False
return True
接下来,我们可以枚举区间内的所有数,对于每个数x,判断是否为双素数。如果x是合数,那么它必然可以分解为两个素数p和q,且p和q都小于等于x的平方根。因此可以枚举p和q,判断它们是否都是素数:
def count_twin_primes(a, b):
count = 0
for x in range(a, b + 1):
if x < 4 or (x % 2 == 0 and x != 2):
continue
for p in range(2, int(x ** 0.5) + 1):
if x % p == 0 and is_prime(p) and is_prime(x // p):
count += 1
break
return count
注意,因为双素数是两个不同的素数的乘积,因此4不是双素数。同时,偶数除了2以外不可能是双素数,因此可以直接跳过。
完整代码如下:
def is_prime(n):
if n < 2:
return False
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return False
return True
def count_twin_primes(a, b):
count = 0
for x in range(a, b + 1):
if x < 4 or (x % 2 == 0 and x != 2):
continue
for p in range(2, int(x ** 0.5) + 1):
if x % p == 0 and is_prime(p) and is_prime(x // p):
count += 1
break
return count
print(count_twin_primes(10, 30)) # 输出2,双素数为15和21
print(count_twin_primes(1, 100)) # 输出8,双素数为15、21、33、35、39、51、55、65