Ajouter un nombre pour obtenir un nombre premier en python

Le code peut être réécrit pour une meilleure lisibilité et des performances améliorées comme suit.

Refactoring du code

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

Amélioration des performances strong>

Résultat:

• 63% plus rapide pour les petits nombres originaux (test 1 ci-dessous)
• 10 fois plus rapide pour des nombres plus grands (test 2 ci-dessous)

Testé avec timeit pour une plus grande précision

Code original transformé en fonction p >

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

Timing Code

Test 1 - Seulement une légère amélioration pour les petits nombres

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

Tester une amélioration de 2 à 10 fois pour de plus grands nombres

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]

La qualité de ce code est autant un problème, de mon point de vue, que la performance. (Les noms de variables a , b , c , d et f , vraiment ?) Le code nécessite une meilleure compréhension des nombres premiers et un peu plus d'attention à la lisibilité du code (et dans une moindre mesure, séparer les tests du code lui-même):

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)

Évitez de mesurer le I / Ô temps d'impression de vos résultats, mesurez simplement le temps qu'il faut pour les calculer.

La réponse à cette question sera.

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

Ce programme est beaucoup plus optimisé car pour la saisie de 99999 nombres, le temps est de 0,38797283172607421875 secondes