Дурацкий способ вывести простые числа в заданном диапазоне

Question

Как писал великий Самуил Яковлевич Маршак, что ни делает дурак, всё он делает не так. Катенька дала дураку Васе Тараканечкину задание: написать программу, выводящую все простые числа в диапазоне, полученном на входе.

Вася сделал следующее (Python-3):

import math
k1=int(input())
k2=int(input())
for i in range (k1, k2+1):
    cnt=0
    for j in range (1, i+1):
        if i%j==0 and math.sqrt( j )-int(math.sqrt( j ))!=0:
            cnt+=j
    if cnt == i:
        print(i)

Насколько Васина программа будет работать медленнее, нежели обычная?

Answer 1

сложность Васиного алгоритма O(n) - это очень неэффективно

алгоритм определения простого числа можно реализовать за O(sqrt(n))

кроме того Васин алгоритм подсчитывает множители - это неэффективно еще и тем, что приходится просмотреть все числа от 1 до i,

хотя если перебирать делители и прерывать перебор, если найден один из делителей - это работает эффективнее

кроме того идет перебор всех чисел в диапазоне [k1, k2], хотя достаточно идти через число, т.е. с шагом 2, потому что из четных простых чисел есть только 1 число - это 2
кроме того использовать код math.sqrt( j )-int(math.sqrt( j ))!=0 нет никакой надобности да и сам код неэффективен, поскольку корень вычисляется 2 раза вместо 1 раза

вообще более-менее эффективный код должен бы выглядеть так:

import math

k1=int(input())
k2=int(input())

if k1 == 2:
    print(k1)

for i in range ((k1 // 2) * 2 + 1, k2 + 1, 2):
    is_prime = true
    for j in range (3, int(math.sqrt(i)) + 1):
        if i % j == 0:
            is_prime = false
            break
    if is_prime:
        print(i)

Answer 2

Пожалуйста поправьте меня если я ошибаюсь, так как я не силен в расчете сложности алгоритмов, но мне видится, что сложность алгоритма Васи можно оценить по формуле суммы членов арифметическое прогрессии: О(n*(k1+k2)/2):

У нас последовательность длиной n, для каждого элемента Вася делает проверку на простоту, ее сложность О(k1) для первого элемента и О(k2) для последнего, то есть суммарная сложность - это сумма О(k1)+O(ki)+O(ki+1)+...+O(k2) или по формуле суммы арифметической прогрессии - О(n*(k1+k2)/2).

Если упростить вычисления, как предложил Zhihar, то длина последовательности сократится вдвое (пропускаем четные элементы), а сложность проверки каждого элемента на простоту будет О(sqrt(n)). Но как теперь посчитать суммарную сложность я не понимаю.

k1,k2 = 2,21
res = [2] if k1==2 else []
is_prime = lambda n,i=2: is_prime(n,i+1) if i*i<=n and n%i else i*i>n

for p in range(k1|1, k2+1, 2): 
    if is_prime(p): res.append(p)

print(*res)  # 2 3 5 7 11 13 17 19

БЛОГ НА HUSL

Дурацкий способ вывести простые числа в заданном диапазоне

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