python经典百题之偶数是2个素数之和

题目:一个偶数表示为两个素数之和。

首先，我们需要明确素数的定义：素数是大于1，且只能被1和自身整除的整数。

下面将分别介绍三种实现方法，每种方法附上解题思路、实现代码、以及优缺点。最后，将对这三种方法进行总结，并推荐其中更好的方法。

方法一: 暴力枚举

解题思路:
暴力枚举所有可能的素数对，检查它们的和是否等于给定的偶数。

实现代码:

def is_prime(num):
    if num < 2:
        return False
    for i in range(2, int(num ** 0.5) + 1):
        if num % i == 0:
            return False
    return True

def find_prime_sum_pairs(even_num):
    primes = [i for i in range(2, even_num) if is_prime(i)]
    pairs = []
    for prime in primes:
        if is_prime(even_num - prime):
            pairs.append((prime, even_num - prime))
    return pairs

# 示例用法
even_num = 20
pairs = find_prime_sum_pairs(even_num)
print(f"Prime pairs that sum up to {even_num}: {pairs}")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

优缺点:

• 优点:
  • 简单易懂，实现简单。
  • 可以找到符合条件的素数对。
• 缺点:
  • 需要遍历所有可能的素数对，时间复杂度较高，不适用于大数字。

方法二: 使用已知素数列表

解题思路:
利用已知的素数列表，从两端开始查找素数对，检查它们的和是否等于给定的偶数。

实现代码:

def is_prime(num):
    if num < 2:
        return False
    for i in range(2, int(num ** 0.5) + 1):
        if num % i == 0:
            return False
    return True

def generate_prime_list(limit):
    primes = []
    for i in range(2, limit + 1):
        if is_prime(i):
            primes.append(i)
    return primes

def find_prime_sum_pairs(even_num, primes):
    pairs = []
    i, j = 0, len(primes) - 1
    while i <= j:
        if primes[i] + primes[j] == even_num:
            pairs.append((primes[i], primes[j]))
            i += 1
            j -= 1
        elif primes[i] + primes[j] < even_num:
            i += 1
        else:
            j -= 1
    return pairs

# 示例用法
even_num = 20
limit = even_num  # Use the even number as the limit to generate primes
primes = generate_prime_list(limit)
pairs = find_prime_sum_pairs(even_num, primes)
print(f"Prime pairs that sum up to {even_num}: {pairs}")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

优缺点:

• 优点:
  • 避免了遍历所有可能的素数对，降低了时间复杂度。
  • 可以找到符合条件的素数对。
• 缺点:
  • 需要预先生成素数列表，占用额外内存空间。
  • 仍然需要判断素数性质，可能存在一定的时间开销。

方法三: 使用素数生成算法

解题思路:
利用素数生成算法（如埃拉托斯特尼筛法）生成素数列表，然后再查找符合条件的素数对。

实现代码:

def generate_primes(limit):
    primes = []
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False

    p = 2
    while p * p <= limit:
        if is_prime[p]:
            for i in range(p * p, limit + 1, p):
                is_prime[i] = False
        p += 1

    for i in range(2, limit + 1):
        if is_prime[i]:
            primes.append(i)

    return primes

def find_prime_sum_pairs(even_num, primes):
    pairs = []
    i, j = 0, len(primes) - 1
    while i <= j:
        if primes[i] + primes[j] == even_num:
            pairs.append((primes[i], primes[j]))
            i += 1
            j -= 1
        elif primes[i] + primes[j] < even_num:
            i += 1
        else:
            j -= 1
    return pairs

# 示例用法
even_num = 20
limit = even_num  # Use the even number as the limit to generate primes
primes = generate_primes(limit)
pairs = find_prime_sum_pairs(even_num, primes)
print(f"Prime pairs that sum up to {even_num}: {pairs}")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

优缺点:

• 优点:
  • 使用素数生成算法生成素数列表，降低了时间复杂度。
  • 可以找到符合条件的素数对。
• 缺点:
  • 需要实现素数生成算法，稍复杂。
  • 仍然需要判断素数性质，可能存在一定的时间开销。

总结与推荐

• 总结:

  • 暴力枚举方法简单直接，但时间复杂度较高，不适用于大数字。
  • 使用已知素数列表方法在暴力枚举的基础上优化了时间复杂度，但需要预先生成素数列表，占用额外内存空间。
  • 使用素数生成算法方法进一步优化了时间复杂度，并避免了预先生成素数列表的内存开销。

• 推荐:

  • 基于素数生成算法的方法是相对更好的选择，因为它在时间和空间上都进行了较好的优化。生成素数的过程虽然稍复杂，但可以节省时间和空间成本，特别在处理大数字时更为高效。