输入形式】 在一行中给出一个(2,2 000 000 000]范围内的偶数N。 【输出形式】 在一行中按照格式“N = p + q”输出N的素数分解,其中p ≤ q均为素数。又因为这样的分解不唯一(例如24还可以分解为7+17),要求必须输出所有解中p最小的解。 【样例输入】 18 【样例输出】 18 = 5 + 13
时间: 2024-03-16 10:47:05 浏览: 15
这道题的思路是使用质数筛选法来找到所有的质数,然后再通过枚举找到符合条件的p和q。具体的实现细节可以参考下面的代码:
```python
import math
# 判断一个数是否为质数
def isPrime(n):
if n <= 1:
return False
for i in range(2, int(math.sqrt(n)) + 1):
if n % i == 0:
return False
return True
# 使用质数筛选法找到所有的质数
def findPrimes(n):
primes = []
isPrime = [True] * (n + 1)
isPrime[0] = isPrime[1] = False
for i in range(2, n + 1):
if isPrime[i]:
primes.append(i)
for j in range(i * i, n + 1, i):
isPrime[j] = False
return primes
# 根据质数列表找到符合条件的p和q
def findPQ(n, primes):
for p in primes:
if p > n // 2:
break
q = n - p
if isPrime(q):
return p, q
return None
# 主函数
if __name__ == '__main__':
n = int(input())
primes = findPrimes(n)
p, q = findPQ(n, primes)
print("{} = {} + {}".format(n, p, q))
```
输入样例:
```
18
```
输出样例:
```
18 = 5 + 13
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)