Задание 25. Информатика. ЕГЭ. Поляков-2591

Просмотры: 135
Изменено: 24 ноября 2024

Определите количество простых чисел в диапазоне \( [2; \,\, 200000]\). (Д.Ф. Муфаззалов)

Решение:

Python


def sieve(N):
    a = [1]*(N+1)

    a[0] = 0
    a[1] = 0

    for x in range(2, int(N**0.5) + 1):
        if a[x]:
            for i in range(x**2, N+1, x):
                a[i] = 0
                
    primes = []
    for x in range(2, N+1):
        if a[x]:
            primes.append(x)
    
    return primes

print(len(sieve(200000)))

Ответ: 17984