Skip to content

57.md

Latest commit

 

History

History
96 lines (73 loc) · 4.44 KB

57.md

File metadata and controls

96 lines (73 loc) · 4.44 KB

五十六、质数

原文：http://inventwithpython.com/bigbookpython/project56.html

质数是只能被 1 和它自己整除的数。质数有各种各样的实际应用，但是没有算法可以预测它们；我们必须一次计算一个。然而，我们知道有无限多的质数有待发现。

这个程序通过强力计算找到质数。它的代码类似于项目 24，“因子寻找器。”（另一种描述质数的方式是，一和数本身是它唯一的因子。）你可以从en.wikipedia.org/wiki/Prime_number那里找到更多关于质数的信息。

运行示例

当您运行primenumbers.py时，输出将如下所示：

Prime Numbers, by Al Sweigart email@protected
`--snip--`
Enter a number to start searching for primes from:
(Try 0 or 1000000000000 (12 zeros) or another number.)
> 0
Press Ctrl-C at any time to quit. Press Enter to begin...
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, `--snip--`

工作原理

isPrime()函数接受一个整数，如果它是质数，则返回True。否则，它返回False。如果你想了解这个项目，项目 24 是值得研究的。isPrime()函数本质上是寻找给定数字中的任何因子，如果找到任何因子，就返回False。

这个程序中的算法可以快速找到大质数。一万亿这个数字只有 10 位数。但是要找到像古戈尔一样大的质数（一个 1 后面跟着 100 个 0），你需要使用一种高级算法，比如 Rabin-Miller 素性测试。我的书《Python 密码破解指南》第 22 章有这个算法的 Python 实现。

"""Prime Numbers, by Al Sweigart email@protected
Calculates prime numbers, which are numbers that are only evenly
divisible by one and themselves. They are used in a variety of practical
applications.
More info at: https://en.wikipedia.org/wiki/Prime_number
This code is available at https://nostarch.com/big-book-small-python-programming
Tags: tiny, math, scrolling"""

import math, sys

def main():
    print('Prime Numbers, by Al Sweigart email@protected')
    print('Prime numbers are numbers that are only evenly divisible by')
    print('one and themselves. They are used in a variety of practical')
    print('applications, but cannot be predicted. They must be')
    print('calculated one at a time.')
    print()
    while True:
        print('Enter a number to start searching for primes from:')
        print('(Try 0 or 1000000000000 (12 zeros) or another number.)')
        response = input('> ')
        if response.isdecimal():
            num = int(response)
            break

    input('Press Ctrl-C at any time to quit. Press Enter to begin...')

    while True:
        # Print out any prime numbers:
        if isPrime(num):
            print(str(num) + ', ', end='', flush=True)
        num = num + 1  # Go to the next number.


def isPrime(number):
    """Returns True if number is prime, otherwise returns False."""
    # Handle special cases:
    if number < 2:
        return False
    elif number == 2:
        return True

    # Try to evenly divide number by all numbers from 2 up to number's
    # square root.
    for i in range(2, int(math.sqrt(number)) + 1):
        if number % i == 0:
            return False
    return True


# If this program was run (instead of imported), run the game:
if __name__ == '__main__':
    try:
        main()
    except KeyboardInterrupt:
        sys.exit()  # When Ctrl-C is pressed, end the program.

探索程序

试着找出下列问题的答案。尝试对代码进行一些修改，然后重新运行程序，看看这些修改有什么影响。

  1. 如果将第 22 行的response.isdecimal()改为response，并输入一个非数字作为开始搜索质数的数字，会出现什么错误？
  2. 如果把第 38 行的number < 2改成number > 2会怎么样？
  3. 如果把第 46 行的number % 1 == 0改成number % i != 0会怎么样？