Как мне ускорить код?

Question

[Андрей Нилл]

Здравствуйте! Написал код по поиску простого числа, на сайте, для которого он написан, не проходит по времени и прерывается. Как мне отредактировать данный код, чтобы не было данной проблемы?

import math
import random
def is_prime(n):
    if n % 2 == 0 and n > 2:
        return False
    return all(n % i for i in range(3, int(math.sqrt(n)) + 1, 2))
k = int(input())
number = 2
i = 0
while True:
    if is_prime(number):
        i += 1
        if i == k:
            break
    number += 1
print(number)

Comments

[o5a]

Андрей Нилл,
k = int(input()) так и есть в коде для сайта? Обычно сайты предлагают грузить входные данные откуда-то, а не использовать input()

[Андрей Нилл]

o5a, Сайту необходимо написать код без входных данных

[Иван Соломенников]

Андрей Нилл, Вам нужная функция которая проверяет простое или составное введенное число?

[Андрей Нилл]

Иван Соломенников, простое

[Иван Соломенников]

Андрей Нилл, Что функция должна возвращать в случае успеха/не успеха?

[Андрей Нилл]

Иван Соломенников, насчёт не успеха в условии задачи не сказано, а в случае успеха вывести K -е простое число

[Иван Соломенников]

Андрей Нилл, ссылку на задачу можно?

[Андрей Нилл]

Иван Соломенников, Ссылку на саму задачу дать не смогу. Только скриншот

[Андрей Нилл]

Bavashi, Нет, код вовсе перестал работать(

[galaxy]

Так не быстрее?

import math
import random

p = []
def is_prime(n):
	qn = int(math.sqrt(n))
	for i in p:
		if i > qn:
			return True
		if n % i == 0:
			return False
	return True

k = 100000
number = 3
i = 1
while True:
	if is_prime(number):
		p.append(number)
		i += 1
		if i == k:
			break
	number += 2

print(number)

(проверяем только нечетные, плюс делители ищем только среди уже найденных простых)

[Андрей Нилл]

galaxy, теперь программа при значении "3" выдаёт ответ "1299709" и происходит это секунд за 15

[Андрей Нилл]

Bavashi, До сих пор выдаёт "Программа выполнялась слишком долго и была прервана"

[Андрей Нилл]

Bavashi,

[Андрей Нилл]

Bavashi, в задаче не написано о том, в каком формате должен выводиться ответ. И странно то, что решение от galaxy неправильно компилируется, но оно проходит по времени на самом сайте

[Андрей Нилл]

Bavashi, когда я локально тестирую код galaxy, то мне выдаётся вот такой ответ:

[Андрей Нилл]

Bavashi, Ахах, блин, точно

[Андрей Нилл]

Bavashi, Проверил задачу на сайте, она опять не проходит по времени. Ну и в компиляторе выполнялось это точно дольше 3-х секунд

[Андрей Нилл]

Bavashi, Сириус, но думаю informatics не отличается, посмотрите там

[Андрей Нилл]

Bavashi, Вроде тут нельзя ссылки кидать

[Андрей Нилл]

Bavashi, Если будет работать, то вот: https://edu.sirius.online/#/course/104/1873/task_7506

[Андрей Нилл]

Bavashi, А на informatics этой задачи нету, но они работают вместе с сириусом и задачи там принимаются так же

[Андрей Нилл]

Bavashi, тогда я не знаю, как вам отправить задачу

[o5a]

Андрей Нилл, решение от galaxy должно проходить по времени, только строку с k соответственно вернуть к виду k = int(input()) чтобы принимало ввод.
Если и так ругается, значит проблема с форматом ввода/вывода. Судя по формулировке ("входной"/"выходной" "файл") возможно на сайте действительно требуется считывать какой-то входной файл и выводить в выходной, а не просто использовать input/print. В таком случае в пределах этого раздела обычно бывают пояснительные примеры.

И не понятно, зачем импортируется модуль random.

Answer 1

[Developer]

как минимум, надо прибавлять не +1, а +2, чтобы не брать чётные числа.
Вот тебе уже ускорение в два раза

А эта дичь вообще тормозная

all(n % i for i in range(3, int(math.sqrt(n)) + 1, 2))

избавься от неё

Answer 2

[galaxy]

Подкину еще вариант:

import math

def npr(k):
    x = 2*k*math.log(k)
    xp = 1
    while abs(x/xp-1) > 0.001:
        xp = x
        x = x - (x - k*math.log(x)) * math.log(x) / (math.log(x) - 1)
    return x

def rwh_primes(n):
    sieve = [True] * n
    for i in range(3,int(n**0.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i]=[False]*((n-i*i-1)//(2*i)+1)
    return [2] + [i for i in range(3,n,2) if sieve[i]]

k = int(input())
print( rwh_primes( int(npr(k)) + 1 )[k-1] )

Как работает:

rwh_primes - решето Эратосфена, не самая быстрая реализация, честно подсмотренная на SO

npr - функция вычисления натурального n, количество простых меньше которого больше или равно k
(на основе неравенства: k > n/ln(n) - функция реализует метод Ньютона для уравнения x/ln(x) = k)