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

Question

Time limit: 0.5 сек.

def is_simple(a):
for j in range(2, int(a ** 0.5) + 1):
    if a % j == 0:
        return False
return True


m, n = map(int, input().split())
arr = []
for i in range(m, n + 1):
    if is_simple(i):
        arr.append(i)
if len(arr) == 0:
    print('Absent')
else:
    print(*arr, sep='\n')

Answer 1

n = int(input())
m = int(input())
p = list(range(m + 1))
p[1] = 0
i = 2
while i <= m:
    if p[i] != 0:
        j = i + i
        while j <= m:
            p[j] = 0
            j = j + i
    i += 1
res=[i for i in p if i != 0 and i >= n]
print(res) if res else print("Absent")

Answer 2

Сегментированное решето Эратосфена:

import math


def primes_in_range(n1, n2):

    def primes_in_range(n1, n2):
        sieve = [True] * (n2 - n1)

        def cross_out(p):
            for i in range((-n1) % p, n2 - n1, p):
                sieve[i] = False

        if 2 < math.isqrt(n2 - 1) + 1:
            cross_out(2)
        for p in range(3, math.isqrt(n2 - 1) + 1, 2):
            cross_out(p)
        return (n1 + i for i, v in enumerate(sieve) if v)

    n1 = max(n1, 2)
    while n1 < n2:
        n = min(n1 ** 2, n2)
        yield from primes_in_range(n1, n)
        n1 = n


def main():
    for p in primes_in_range(*map(int, input().split())):
        print(p)


main()

Решето хранится для полуинтервала [n₁, n₂). cross_out(p) вычеркивает из решета все числа кратные p. Из-за особенностей решения нужно чтобы было n₂ ≤ n₁². Если полуинтервал больше, он обрабатывается в несколько приемов.

Что можно успеть за полсекунды:

$ time echo 1 1_350_000 | python segmented-sieve-0.py > temp_0.txt

real  0m0.479s
user  0m0.480s
sys   0m0.000s

$ time echo 1_000_000_000 1_001_000_000 | python segmented-sieve-0.py > temp_0.txt

real  0m0.496s
user  0m0.484s
sys   0m0.008s

$ time echo 1_000_000_000_000 1_000_000_500_000 | python segmented-sieve-0.py > temp_0.txt

real  0m0.494s
user  0m0.488s
sys   0m0.008s

Потребление памяти можно снизить в восемь раз, если заменить обычный список на bytearray. Скорость тоже вырастет немного:

def primes_in_range(n1, n2):

    def primes_in_range(n1, n2):
        sieve = bytearray(n2 - n1)

        def cross_out(p):
            for i in range((-n1) % p, n2 - n1, p):
                sieve[i] = 1

        if 2 < math.isqrt(n2 - 1) + 1:
            cross_out(2)
        for p in range(3, math.isqrt(n2 - 1) + 1, 2):
            cross_out(p)
        return (n1 + i for i, v in enumerate(sieve) if v == 0)

    n1 = max(n1, 2)
    while n1 < n2:
        n = min(n1 ** 2, n2)
        yield from primes_in_range(n1, n)
        n1 = n

В решете можно не хранить флаги для чётных чисел. Потребление памяти снизится ещё в два раза. Скорость вырастет примерно в два раза. Код станет даже проще в каком-то смысле:

def primes_in_range(n1, n2):

    def primes_in_range(n1, n2):
        sieve = bytearray((n2 - n1) // 2)
        for p in range(3, math.isqrt(n2 - 1) + 1, 2):
            for i in range(((p - n1) // 2) % p, (n2 - n1) // 2, p):
                sieve[i] = 1
        return (n1 + 2 * i for i, v in enumerate(sieve) if v == 0)

    if n1 <= 2 < n2:
        yield 2
   
    n1 = max(n1 + 1 - n1 % 2, 3)
    n2 += 1 - n2 % 2
    while n1 < n2:
        n = min(n1 ** 2, n2)
        yield from primes_in_range(n1, n)
        n1 = n

Что можно успеть за полсекунды:

$ time echo 1 3_600_000 | python segmented-sieve-2.py > temp_2.txt

real  0m0.489s
user  0m0.480s
sys   0m0.008s

$ time echo 1_000_000_000 1_003_200_000 | python segmented-sieve-2.py > temp_2.txt

real  0m0.496s
user  0m0.488s
sys   0m0.004s

$ time echo 1_000_000_000_000 1_000_001_300_000 | python segmented-sieve-2.py > temp_2.txt

real  0m0.499s
user  0m0.492s
sys   0m0.004s

БЛОГ НА HUSL

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

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