python-3.x - 如何找到给定范围内的所有素数？

Question

def all primes(start,end):
    list_primes = []
    for i in range(start,end):
        for a in range(2,i):
            if i % a == 0:
                list_primes.append(i)

    return list_primes

由于某种原因，它返回除素数之外的所有内容。它可能是一些愚蠢的错误。任何人都可以帮忙吗？

Answer 1

将您的内部循环更改为：

for a in range(2,i):
    if i % a == 0:
        break
else:
    list_primes.append(i)

从这里复制粘贴:-)
顺便说一下，他们使用了相同的代码，例如 :)

Answer 2

试试这个（使用 Eratosthenes 筛）：

    def all_primes(start, end):
        return list(sorted(set(range(start,end+1)).difference(set((p * f) for p in range(2, int(end ** 0.5) + 2) for f in range(2, (end/p) + 1)))))

Answer 3

我想分享一下我发现在一个范围内生成素数的最快方法是使用SymPy 符号数学库：

import sympy 

def all_primes(start, end):
    return list(sympy.sieve.primerange(start, end))

该sympy.sieve.primerange()函数返回一个生成器，因此我们需要list()将其转换为列表。

这是此线程中当前最受好评的已经非常优化的答案之间的性能差异示例：

import sympy

def get_primes_python(start, stop):
    dct = {x: True for x in list(range(start, stop+1))}
    x = start

    while x ** 2 <= stop:
        if dct[x]:
            y = x ** 2
            while y <= stop:
                dct[y] = False
                y += x
        x += 1

    lst = []
    for x, y in dct.items():
        if y:
            lst.append(x)

    return lst

def get_primes_sympy(start, stop):
    return list(sympy.sieve.primerange(start, stop))

In [2]: %timeit test.get_primes_python(1, 10**7)
1 loop, best of 3: 4.21 s per loop

In [3]: %timeit test.get_primes_sympy(1, 10**7)
10 loops, best of 3: 138 ms per loop

Answer 4

要获取素数，请尝试实施埃拉托色尼筛法https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

在 Python 3 中寻找 100 万个数字，对我来说大约需要 0.5 秒

def get_primes(start, stop):
    dct = {x: True for x in list(range(start, stop+1))}
    x = start

    while x ** 2 <= stop:
        if dct[x]:
            y = x ** 2
            while y <= stop:
                dct[y] = False
                y += x
        x += 1

    lst = []
    for x, y in dct.items():
        if y:
            lst.append(x)

    return lst

res = get_primes(2, 1000000)
print(res)

Answer 5

你可以试试这个功能

def generate_primes(lower_limit,upper_limit):
    if not isprime(lower_limit):
        return False
    candidate = lower_limit
    r = []
    while(candidate <= upper_limit):
        trial_divisor = 2
        prime = 1 # assume it's prime
        while(trial_divisor**2 <= candidate and prime):
            if(candidate%trial_divisor == 0):
                prime = 0 # it isn't prime
            trial_divisor+=1
        if(prime):
            r += [candidate]
        candidate += 2
    return r

def isprime(n):
    '''check if integer n is a prime'''
    # make sure n is a positive integer
    n = abs(int(n))
    # 0 and 1 are not primes
    if n < 2:
        return False
    # 2 is the only even prime number
    if n == 2: 
        return True    
    # all other even numbers are not primes
    if not n & 1: 
        return False
    # range starts with 3 and only needs to go up the squareroot of n
    # for all odd numbers
    for x in range(3, int(n**0.5)+1, 2):
        if n % x == 0:
            return False
    return True

我是从这个页面修改的http://dunningrb.wordpress.com/2009/02/12/prime-numbers-and-a-simple-python-code/

Answer 6

尝试这个：

def isprime (x):
    isprime=True
    if x!=2:
        for i in range (2,x):
            if x%2==0:
                isprime=False
            break
        return isprime
x=int(input("enter a number"))
z=isprime(x)
print(z)