求1000以内的素数python

本文将从多个方面详细阐述如何使用Python来求解1000以内的素数问题。

一、素数的定义

素数是指只能被1和本身整除的自然数。简单来说，就是只有1和本身两个因数的自然数。

例如，2、3、5、7、11等都是素数。而4、6、8、9等不是素数，因为它们还能被其他数字整除。

二、筛选法求解素数

筛选法也叫埃氏筛法，其基本思想是，先将2~1000的数存入一个列表中，然后依次筛除2的倍数、3的倍数、5的倍数、7的倍数等，最后剩下的就是所有的素数。

代码如下：

def sieve_of_eratosthenes(n):
    prime_list = [i for i in range(2, n+1)]  # 初始化prime_list，存储2~n的数字
    p = 2
    while p * p <= n:
        if p in prime_list:
            # 筛选掉p的倍数
            for i in range(p * 2, n + 1, p):
                if i in prime_list:
                    prime_list.remove(i)
        p += 1
    return prime_list

print(sieve_of_eratosthenes(1000))

三、试除法求解素数

试除法是最基本的素数判定方法。它的基本思想是，对待判断数n，用2到n-1之间的所有整数依次对n进行除法运算，如果都不能整除，则n是素数。

代码如下：

def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

prime_list = [i for i in range(2, 1001) if is_prime(i)]
print(prime_list)

四、Miller-Rabin算法求解素数

Miller-Rabin算法是一种快速判断大数是否为素数的算法。它的基本思想是，对于大数n，随机取一个小于n的整数a，计算a^(n-1) mod n的值，如果不等于1，则n一定不是素数；如果等于1，则需要进一步进行计算，直到满足一定条件为止。

代码如下：

import random

def check(a, s, d, n):
    x = pow(a, d, n)
    if x == 1:
        return True
    for i in range(s - 1):
        x = pow(x, 2, n)
        if x == n - 1:
            return True
    return False

def is_prime(n, k=5):
    if n == 2 or n == 3:
        return True
    if n < 2 or n % 2 == 0:
        return False

    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1

    for i in range(k):
        a = random.randrange(2, n - 1)
        if not check(a, s, d, n):
            return False
    return True

prime_list = [i for i in range(2, 1001) if is_prime(i)]
print(prime_list)

五、结语

本文介绍了三种求解1000以内素数的方法，分别是筛选法、试除法和Miller-Rabin算法。读者可以根据自己的需要选择适合的方法来求解素数问题。