寻找素数不同的方法

Question

我试图制作一个程序，为公钥密码系统查找素数。我知道素数是一个正整数，除了1和它本身没有正数除数。我想使用一种从2到sqrt(n)的所有整数的方法，来判断它是否除以n。

我必须采取“蛮力”的方法，它接受一个整数输入种子，并返回最低素数；prime number >= seed。

我想要的一些例子是：

>>> prime_func(100)
101
>>> prime_func(1000)
1009
>>>prime_func(7)
7
>>>prime_func(3)
5

到目前为止，我得到的是：

def prime_func(number):

    START = 2
    END = (number**0.5) + 1

    for i in range(START, END):
      if number % i == 0:
         return('Composite')
      else:
         return number

对于return ('Composite')部分，我希望它在此之后返回最近的素数。

Answer 1

尝试以下代码：

def prime_func(number):
    number = int(number)
    START = 2
    END = int((number**0.5)) + 1

    if number == 2:
     return 1
    if number == 1:
     return 0

    while True:
        flag = True
        for i in range(START, END):
            if number % i == 0:
                flag = False
                break
        if flag:
            return number
        else:
            number += 1

if __name__ == '__main__':
    num = int(input())
    print(prime_func(num))

输入： 100

输出： 101

输入： 1000

输出： 1009

Answer 2

这可以使用埃拉托斯提尼筛来实现。

代码：

def primes_sieve(limit):
    a = [True] * limit                          # Initialize the primality list
    a[0] = a[1] = False

    for (i, isprime) in enumerate(a):
        if isprime:
            yield i
            for n in range(i*i, limit, i):     # Mark factors non-prime
                a[n] = False

for value in primes_sieve(32):
    print(value)

输出：

2
3
5
7
11
13
17
19
23
29
31

见这篇文章。