从零开始的Python ACM Ch.5：练习系列

784 字

4 分钟

从零开始的Python ACM Ch.5：练习系列

2022-11-01

Coding

求素数#

问题描述求给定范围start、end之间的所有素数。
问题分析素数指的是只能被1和它自身整除的整数。判定一个整数m是否为素数的关键，就是要判定整数m能否能被除1和它自身以外的其他任何整数所整除，若都不能整除，则m为素数。本题求的是给定范围start、end之间的所有素数，考虑到程序的通用性，需要从键盘输入start和end的值，例如输入sta：1，end=1000，则所编写的程序应能够打印出1、1000之间的所有素数。
求素数的方法参考：判断一个数是否为质数（素数）的4种方法_是杰夫呀的博客-CSDN博客_如何判断一个数是不是质数

1
from math import sqrt
2

3
start = int(input('Start: '))
4
end = int(input('End: '))
5

6

7
def isPrime(num):
8
    if num == 2: return True
9
    if num % 2 == 0: return False
10
    i = 3
11
    while i <= sqrt(num):
12
        if num % i == 0: return False
13
        i += 2
14
    return True
15

16

17
for i in range(start, end + 1):
18
    if isPrime(i):
19
        print(i)

哥德巴赫猜想#

问题描述 2000以内的不小于4的正偶数都能够分解为两个素数之和（即验证歌德巴赫猜想对2000以内的正偶数成立）。
问题分析根据问题描述，为了验证歌德巴赫猜想对2000以内的正偶数都是成立的，要将整数分解为两部分，然后判断分解出的两个整数是否均为素数。若是，则满足题意，否则应重新进行分解和判断。针对该问题，我们可以给定如下的输入和输出限定。输入时：每行输入一组数据，即2000以内的正偶数n，一直输入到文件结束符为止。输出时：输出n能被分解成的素数a和b。如果不止一组解，则输出其中a最小的那组解。当然，读者可以根据实际的需要规定不同的输入和输出形式。
这里指定输入方式：从控制台读入，空格分割

1
from math import sqrt
2

3
nums = input('Nums(split with space): ').split()
4

5

6
def isPrime(num):
7
    if num == 2: return True
8
    if num % 2 == 0: return False
9
    i = 3
10
    while i <= sqrt(num):
11
        if num % i == 0: return False
12
        i += 2
13
    return True
14

15
nums = list(map(int, nums))
16
for num in nums:
17
    add1 = -1
18
    add2 = -1
19
    for i in range(2, num):
20
        if not isPrime(i): continue
21
        else:
22
            for j in range(num, 1, -1):
23
                if not isPrime(j): continue
24
                else:
25
                    if i + j == num:
26
                        add1 = i
27
                        add2 = j
28
                        break
29
        if add1 != -1 and add2 != -1: break
30
    print(add1, add2)

输入与输出

1
Nums(split with space): 4 5 6 7 8 9 10
2
2 2
3
2 3
4
3 3
5
2 5
6
3 5
7
2 7
8
3 7

1898#

问题描述：“1898一要发就发”。请将不超过1993的所有素数从小到大排成第一行，第二行上的每个数都等于它上面相邻两个素数之差。编程求出：第二行数中是否存在若干个连续的整数，它们的和恰好为1898？假如存在的话，又有几种这样的情况？两行数据分别如下：第一行：2，3，5，7，11，13，17 …… 1979，1987，1993

第二行：1，2，2，4，2，4……8，6

（还没做）