Не понимаю работу алгоритма

Question

def eratosthenes2(n):
    multiples = set()
    for i in range(2, n+1):
        if i not in multiples:
            yield i
            multiples.update(range(i*i, n+1, i))

Не понимаю, как работает алгоритм "Решето Эратосфена" или другой алгоритм, который вычисляет простое число или нет. Из-за непонимания этого алгоритма и написал так:

class Human:
    n = 600851475143
    s = 2
    asd = []

    def xiao(self):
        i = 1
        while i <= self.s:
            if self.s % i == 0:
                self.asd.append(i)
            if i >= self.s:
                self.Dir()
            i += 1

    def Dir(self):
        if self.s >= 486849:
            return
        if len(self.asd) == 2:
            self.asd.clear()
            print(self.s)
            self.s += 1
            self.DgunLi()
        else:
            self.s += 1
            self.DgunLi()

    def DgunLi(self):
        running = True
        while running:
            if self.s >= 486849:
                break
            if self.s % 2 != 0 and self.n % self.s == 0:
                running = False
                self.xiao()
            else:
                self.s += 1

Human().DgunLi()

Моих знаний не хватило написать что-то лучше. Не могли бы вы мне объяснить, как работает "Решето Эратосфена" или любой другой удобный алгоритм для вычисления простых чисел. Настолько подробно, насколько возможно.

Answer 1

Просто́е число́ — натуральное (целое положительное) число, имеющее ровно два различных натуральных делителя — единицу и самого себя. Другими словами, число x является простым, если оно больше 1 и при этом делится без остатка только на 1 и на x.

Вот решение простой задачки, когда на вход даётся список чисел и нужно посчитать сколько в этом списке простых чисел. Для решения используется "любой другой удобный алгоритм", а именно простой перебор:

array = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 1, 2, 3, 5, 8, 24, 777]

counter = 0
for number in array:
    for divider in range(number + 1):
        if divider != 0 and number % divider == 0 and divider not in [number, 1] or number == 1:
            break
        else:
            counter += 1

print('В последовательности найдено простых чисел:', counter)

БЛОГ НА HUSL

Не понимаю работу алгоритма

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