Задача к ЕГЭ по информатике на тему «Особые числа (простые, фибоначи, факториал, палиндромы)» №1

Просмотров 11 Комментарии 0

Напишите программу, которая ищет количество простых чисел, принадлежащих числовому отрезку $[1000000;5000000]$ .

Решение 1

Классическое неэффективное решение через перебор, которое умирает на больших диапазонах

def is_prime(n):
    if n == 1: return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True
count = 0
for i in range(1000000, 5000000 + 1):
    if is_prime(i): count += 1
print(count)

Решение 2

Эффективное решение задачи с помощью алгоритма «Решето Эратосфена»

def resheto(n):
    a = [1] * (n + 1)
    a[0] = a[1] = 0
    for i in range(2, int(n**0.5) + 1):
        if a[i]:
            for j in range(i, n // i + 1):
                a[i * j] = 0
    return a
print(sum(resheto(5000000)) - sum(resheto(999999)))

Ответ: 270015