Оптимизация поиска количества простых чисел, меньших заданного числа n

Question

Задание: посчитать количество простых чисел, меньших заданного числа 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

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

Answer 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)

Answer 2

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

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)

Answer 3

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

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 сравнение различных реализаций

БЛОГ НА HUSL

Оптимизация поиска количества простых чисел, меньших заданного числа n

Ответы (3 шт):