添加一个数字以获得 python 中的质数

Question

程序是求一个数最接近的素数。我解决了问题，但我想优化代码。

import time
def isprime(a ,d):
    b=a
    c=0
    f=b**(0.5)
    for i in range(1,int(f)+1):
        if a%i==0 and c<=1:
            c+=1
    if c==1:
        return d.append(b)
    else:
        b=a+1
        isprime(b,d)

start=time.time()        
b=[89, 54,36, 74, 44, 19, 12]   # Input
d=[]
for i in b:
    isprime(i,d)     #function call
print(d)             #output is [89, 59, 37, 79, 47, 19, 13]
stop=time.time()
print(stop-start)    #0.0001347064971923828 Seconds

帮助优化代码。我只是一个初学者，我知道代码比较低。帮助学习一些编码。

Answer 1

可以如下重写代码以提高可读性和性能。

代码重构

def is_prime(n):
  " Returns True if prime False otherwise "

  # Base cases
  if n < 2:
    return False
  if n == 2:
    return True
  if n % 2 == 0:
    return False

  # checking odd numbers 3, 5, ...
  return next((False for i in range(3, int(n**0.5) + 1, 2) if n % i == 0), True)

def next_prime(n):
  " First prime number greater or equal to n "
  if n <= 2:
    return 2

  while not is_prime(n):
    if n % 2:
      n += 2  # stay on odd
    else:
      n += 1  # switch to odd

  return n

def next_prime_batch(b):
  " Finds next prime for a batch of numbers "
  return [next_prime(x) for x in b]

性能提升

结果：

原始小数字快 63%（下面的测试 1）
大数字快 10 倍（下面的测试 2）

测试

使用 timeit 进行测试以获得更高的准确性

原代码制作成函数

def isprime(a, d):
    b=a
    c=0
    f=b**(0.5)

    for i in range(1,int(f)+1):
        if a%i==0 and c<=1:
            c+=1

    if c==1:
        return d.append(b)
    else:
        b=a+1
        isprime(b,d)

def calc_next_primes(b):
  d=[]
  for i in b:
      isprime(i,d)     #function call
  return b

时序码

测试 1 -- 对于较小的数字只有轻微的改进

b = [2, 89, 54,36, 74, 44, 19, 12]
count = 10000  # number of timing iterations
print(timeit(lambda: calc_next_primes(b), number = count))
print(timeit(lambda: next_prime_batch(b), number = count))
# calc_next_primes: 1.4129 seconds for 10K iterations
# next_prime_batch: 0.8683 seconds for 10K iterations

测试 2--10 倍的改进对于更大的数字

b = [12346, 1920131, 219112, 1423231]
count = 1000  # number of timing iterations
print(timeit(lambda: calc_next_primes(b), number = count))
print(timeit(lambda: next_prime_batch(b), number = count))
# calc_next_primes: 7.8703 seconds for 1K iterations
# next_prime_batch: 0.6200 seconds for 1K iterations

Answer 2

在我看来，此代码的质量与性能一样重要。（变量名称 a、b、c、d 和 f，真的吗？）注意代码的可读性（在较小程度上，将测试与代码本身分开）：

def is_odd_prime(number):

    for divisor in range(3, int(number ** 0.5) + 1, 2):
        if number % divisor == 0:
            return False

    return True

def prime_ceiling(number):

    if number <= 2:
        return 2

    number |= 1  # enforce odd

    while not is_odd_prime(number):
        number += 2

    return number

if __name__ == "__main__":

    from time import time

    numbers = [89, 54, 36, 74, 44, 19, 12]

    start = time()

    primes = [prime_ceiling(number) for number in numbers]

    stop = time()

    print(primes)
    print(stop - start)

避免测量 I/O 打印结果的时间，只需测量计算结果所需的时间。

Answer 3

这个问题的答案是。

from math import sqrt
from time import time
def prime_no(n):
    if n==1:
        return False 
    if n<=3:
        return True 
    if n%2==0 or n%3==0:
        return False 
    for i in range(5,int(sqrt(n))+1,6):
        if n%i==0 or n%(i+2)==0:
            return False 
    return True
a=time()
l=[89, 54,36, 74, 44, 19, 12]   #input
maxi=max(l)
while (prime_no(maxi)==False):
    maxi+=1 
k=[True for i in range(maxi+1)]
p=2 
while(p*p<=maxi):
    if(k[p]==True):
        for i in range(p*p,maxi+1,p):
            k[i]=False 
    p+=1 
for i in l:
    f=i
    while k[f]==False:
        f+=1 
    print(f,end=' ')
z=time()
print("Time: {:.20f}".format(z-a))    #89 59 37 79 47 19 13 Time: 0.00011634826660156250

本程序优化很多，输入99999个数字耗时0.38797283172607421875秒

添加一个数字以获得 python 中的质数

Add a number to get prime number in python

python

optimization

primes