Как я могу заставить этот код Python работать быстрее? [Проект Эйлера Проблема № 7]

Question

Я пытаюсь выполнить эту задачу Project Euler:

Перечислив первые шесть простых чисел: 2, 3, 5, 7, 11 и 13, мы увидим, что 6-е числопростое число 13.

Что такое 10 001-е простое число?

Мой код кажется правильным, потому что он работает с небольшими числами, например, 6-е простое число - 13.

Как я могу улучшить его, чтобы код работал намного быстрее для больших чисел, таких как 10 001.

Код указан ниже:

#Checks if a number is a prime
def is_prime(n):
    count = 0
    for i in range(2, n):
        if n%i == 0:
            return False
            break
        else:
            count += 1
    if count == n-2:
        return True

#Finds the value for the given nth term     
def term(n):
    x = 0
    count = 0
    while count != n:
        x += 1
        if is_prime(x) == True:
            count += 1
    print x


term(10001)

ОБНОВЛЕНИЕ:

Спасибо за ваши ответы.Я должен был быть более ясным, я не стремлюсь ускорить интерпретатор или найти более быстрый интерпретатор, потому что я знаю, что мой код не очень хорош, поэтому я искал способы сделать мой код более эффективным.

Answer 1

Несколько вопросов для размышления:

• Вам действительно нужно проверять деление до n-1? Как раньше ты можешь остановиться?
• Помимо 2, вам действительно нужно проверить деление на все кратные двум?
• А как насчет кратных 3? 5? Есть ли способ распространить эту идею на все кратные числа ранее проверенных простых чисел?

Answer 2

Цель Project Euler - не думать о программировании, а думать о алгоритмах . В задаче № 10 ваш алгоритм должен быть даже быстрее, чем в № 7 и т. Д. И т. Д. Поэтому вам нужно найти лучший способ найти простые числа, а не более быстрый способ запуска кода Python. Люди решают эти проблемы в сжатые сроки с гораздо более медленными компьютерами, которые вы используете сейчас, думая о математике .

В этой заметке, возможно, спросите о вашем алгоритме простых чисел на https://math.stackexchange.com/, если вам действительно нужна помощь, чтобы подумать о проблеме.

Answer 3

Многие из проблем Эйлера (включая эту) предназначены для решения, которое вычисляет в приемлемое время практически на любом аппаратном обеспечении и компиляторе (ну, может быть, не INTERCAL на PDP-11).

Ваш алгоритм работает, но он имеет квадратичную сложность.Использование более быстрого интерпретатора даст вам линейное повышение производительности, но квадратичная сложность превзойдет его задолго до того, как вы вычислите 10000 простых чисел.Есть алгоритмы с гораздо меньшей сложностью;найдите их (или погуглите их, в этом нет ничего постыдного, и вы еще многому научитесь) и реализуйте их.

Answer 4

Более быстрый переводчик этого не сделает. Даже реализация, написанная на C или ассемблере, не будет достаточно быстрой (чтобы быть в «примерно одной секунде» времени проекта Euler). Проще говоря, ваш алгоритм жалок. Некоторые исследования и размышления помогут вам написать алгоритм, который работает в собачьем медленном интерпретаторе быстрее, чем ваш текущий алгоритм, реализованный в нативном коде (я не буду называть никаких подробностей, отчасти потому, что это ваша работа, а отчасти потому, что я не могу сказать об этом случайно) сколько потребуется оптимизации).

Answer 5

Без обсуждения вашего алгоритма интерпретатор PyPy может быть смехотворно быстрее обычного интерпретатора CPython для таких жестких численных вычислений, как этот.Вы можете попробовать это.

Answer 6

чтобы проверить простое число, которое вам не нужно запускать до n-1 или n / 2 ....

Чтобы запустить его быстрее, вы можете проверить только до получения квадратного корня из n

И это самый быстрый алгоритм, который я знаю

def isprime(number):
        if number<=1:
            return False
        if number==2:
            return True
        if number%2==0:
            return False
        for i in range(3,int(sqrt(number))+1):
            if number%i==0:
                return False
        return True

Answer 7

Другое быстрое решение Python:

import math
prime_number = 4 # Because 2 and 3 are already prime numbers
k = 3 # It is the 3rd try after 2 and 3 prime numbers
milestone = 10001
while k <= milestone:
    divisible = 0
    for i in range(2, int(math.sqrt(prime_number)) + 1):
        remainder = prime_number % i
        if remainder == 0: #Check if the number is evenly divisible (not prime) by i
            divisible += 1
    if divisible == 0:
        k += 1
    prime_number += 1
print(prime_number-1)

Answer 8

Я подошел к этому по-другому. Мы знаем, что все кратные 2 не будут простыми (кроме 2), мы также знаем, что все не простые числа могут быть разбиты на простые составляющие.

т.е.

12 = 3 х 4 = 3 х 2 х 2

30 = 5 х 6 = 5 х 3 х 2

Поэтому я перебрал список нечетных чисел, накапливал список простых чисел и пытался найти только модуль нечетных чисел с простыми числами в этом списке.

#First I create a helper method to determine if it's a prime that 
#iterates through the list of primes I already have
def is_prime(number, list):
    for prime in list:
        if number % prime == 0:
            return False
    return True

РЕДАКТИРОВАТЬ: Первоначально я написал это рекурсивно, но я думаю, что итеративный случай намного проще

def find_10001st_iteratively():
    number_of_primes = 0
    current_number = 3
    list_of_primes = [2]
    while number_of_primes <= 10001:
        if is_prime(current_number, list_of_primes):
            list_of_primes.append(current_number)
            number_of_primes += 1
        current_number += 2
    return current_number

Answer 9

Питонический ответ

import time
t=time.time()
def prime_bellow(n):
   b=[]
   num=2
   j=0
   b.append(2)
   while len(b)-1<n:
        if all(num%i!=0 for i in range(2,int((num)**0.5)+1)):
            b.append(num)
        num += 1
   print b[n]
 prime_bellow(10001)
 print time.time()-t

Печать

104743

   0.702000141144 second

Answer 10

import time
t=time.time()
def n_th_prime(n):

    b=[]
    b.append(2)
    while len(b)<n :
        for num in range(3,n*11,2):
            if all(num%i!=0 for i in range(2,int((num)**0.5)+1)):
                b.append(num)


    print list(sorted(b))[n-1]
n_th_prime(10001)
print time.time()-t

отпечатков

104743

0,569000005722 секунды