Добавьте число, чтобы получить простое число в python - PullRequest
Новая
       92

Добавьте число, чтобы получить простое число в python

1 голос
/ 19 июня 2020

Программа предназначена для получения ближайшего простого числа к числу. Я решил проблему, но использую sh для оптимизации кода. 

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

Помощь в оптимизации кода. Я только новичок, знаю, что код ниже. Помогите разобраться в коде.

Ответы [ 3 ]

0 голосов
/ 20 июня 2020

Качество этого кода, с моей точки зрения, является такой же проблемой, как и производительность. (Имена переменных 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)

Избегайте измерения времени ввода-вывода для печати ваших результатов, просто измерьте, сколько времени потребуется для их вычисления.

0 голосов
/ 20 июня 2020

Ответ на этот вопрос будет. 

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 секунд

0 голосов
/ 20 июня 2020

Код можно переписать для облегчения чтения и повышения производительности следующим образом.

Рефакторинг кода 

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
...