Python 不大于n的最大素数？

Question

Python 不大于n的最大素数？输入一个正整数n>1 十一点就要提交了，为什么不对啊！

Answer 1

可以使用下面的算法计算不大于n的最大素数:

def largest_prime_below(n):
    if n <= 2:
        return None
    primes = [2]
    i = 3
    while i <= n:
        is_prime = True
        for p in primes:
            if i % p == 0:
                is_prime = False
                break
        if is_prime:
            primes.append(i)
        i += 2
    return primes[-1]

这个算法的思路是:1. 先定义一个素数列表primes,初始化为[2]2. 从i=3开始遍历,因为2是唯一的偶素数3. 对每个i,判断它是否是素数:- 取primes中的每个素数p,判断i是否能被p整除

• 如果能被整除,则i不是素数,break退出本次循环
• 如果i不能被任何素数整除,则i是素数,将i添加到primes中4. 重复步骤3,直到i>n为止5. 返回primes中的最后一个素数,这是不大于n的最大素数例如,输入n=97,该算法的执行过程是:i=3,primes=[2],3是素数,primes=[2,3]
  i=5,primes=[2,3],5是素数,primes=[2,3,5]
  i=7,primes=[2,3,5],7是素数,primes=[2,3,5,7]
  ...
  i=97,primes=[2,3,5,7,11,...,83],83是最大素数所以,返回83,这是不大于97的最大素数。