3

Задание: посчитать количество простых чисел, меньших заданного числа n. Мой код:

def prime(n):
    for i in range(2, n):
        for j in range(2, 1000):
            if i < j:
                break
            if i % j == 0 and i != j:
                n -= 1
                break
    if n <= 2:
        return 0
    return n - 2

не проходит лимит по времени, как можно сократить затрачиваемое время?

2
  • Почитать хоть что-нибудь по алгоритмам поиска простых чисел. Если лениво думать самостоятельно, то поискать на этом сайте и найти десяток вопросов на эту тему. 9 мар 2020 в 7:05
  • Что делать с ответами на мой вопрос?. У вас ещё нет принятых ответов ни в одной теме. Неужели ни один не помог?
    – 0xdb
    14 мар 2020 в 19:49

3 ответа 3

4

Оптимизированный алгоритм решета Эратосфена:

def primes(n):
    """ Returns  a list of primes < n """
    # (c) Robert William Hanks - https://stackoverflow.com/a/3035188/5741205
    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]]

еще более оптимизированная реализация того же алгоритма за счёт использования bytearray и itertools.compress:

from itertools import compress

def primes(n):
    # (c) Bruno Astrolino - https://stackoverflow.com/a/46635266/5741205
    sieve = bytearray([True]) * (n//2)
    for i in range(3,int(n**0.5)+1,2):
        if sieve[i//2]:
            sieve[i*i//2::i] = bytearray((n-i*i-1)//(2*i)+1)
    return [2,*compress(range(3,n,2), sieve[1:])]

использование:

res = len(primes(n))

PS самый быстрый алгоритм из известных мне для обычного Python (есть более ьыстрые реализации с использованием Numpy)

PPS сравнение различных реализаций

1
import math
    s = set(range(1, n, 2))
    for i in range(2, int(math.sqrt(n))):
        if i in s: 
            s -= set(range(i*i, n, i))
    return len(s)
0

Воспользуйтесь Решетом Эратосфена:

def primes_to(n:int)->int:
    a = [i for i in range(n)]
    a[1] = 0
    for i in range(2, n):
        if a[i]:
            for j in range(2*i, n, i):
                a[j] = 0
    a = set(a)
    a.remove(0)
    return len(a)
0

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.