У меня проблема с кодом на Сите Эратосфена - PullRequest
Новая
       79

У меня проблема с кодом на Сите Эратосфена

0 голосов
/ 12 июля 2020

См. Мой код ниже. Я все время получаю код ошибки и тоже не понимаю, что это значит. Где в коде я могу посмотреть? 

def list_true(n):
    return [False for x in range(2)] + [x for x in range (2, n+1)]

assert len(list_true(20)) == 21
assert list_true(20)[0] is False
assert list_true(20)[1] is False


def mark_false(bool_list, p):
    mark_false = []
    for x in bool_list:
        if x/p == 1:
            mark_false.append(True)
        elif x % p == 0:
            mark_false.append(False)
        else:
            mark_false.append(True)
    return mark_false

assert mark_false(list_true(6), 2) == [False, False, True, True, False, True, False]

def find_next(bool_list, p):
    x = 0
    cleared = False
    for bool in bool_list:
        if cleared:
            if bool:
                return x
        if x == p and bool:
            cleared = True
        x += 1
    return None

assert find_next([True, True, True, True], 2) == 3
assert find_next([True, True, True, False], 2) is None

def prime_from_list(bool_list):
    y = [x for x, i in enumerate(bool_list) if i]
    prime_from_list = []
    for element in bool_list:
        if element == True:
            return y
    return prime_from_list

assert prime_from_list([False, False, True, True, False]) ==  [2, 3]

def sieve(n):
    bool_list = list_true(n)
    p = 2
    while p is not None:
        bool_list = mark_false(bool_list, p)
        p = find_next(bool_list, p)
    return prime_from_list(bool_list)

Затем я получаю сообщение об ошибке после кода ниже. 

assert sieve(1000) == get_primes(0, 1000)
--------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
<ipython-input-50-c49169fabbae> in <module>()
----> 1 assert sieve(1000) == get_primes(0, 1000)

AssertionError:

Почему я получаю сообщение об ошибке и есть ли способ можно поправить?

1 Ответ

0 голосов
/ 12 июля 2020

Это странный вопрос. Во-первых, вы не указали get_primes(0, 1000), поэтому мы не можем сравнивать результаты. Во-вторых, вы, как программист, вставляете операторы assert для проверки ситуаций, которых, как вы знаете, не должно произойти, поэтому вы не должны подвергать сомнению сам assert.

Я считаю, что причина в assert не работает, потому что ваш замученный код не производит простых чисел (он включает составные нечетные числа). Например, sieve(20) возвращает: 

[2, 3, 5, 7, 9, 11, 13, 15, 17, 19]

Более того, ваш код на самом деле не решето! Подпрограмма mark_false() должна просто вычеркивать числа, кратные последнему открытому простому числу, но вместо этого проверяет все числа, чтобы увидеть, делятся ли они на простое! Это грубая сила первичный поиск под видом сита.

Ниже я переделал и упростил ваш код, который должен передать рассматриваемое утверждение: 

def list_true(n):
    return [False for _ in range(2)] + [True for _ in range(2, n + 1)]

assert len(list_true(20)) == 21
assert list_true(20)[0] is False
assert list_true(20)[19] is True

def mark_false(bool_list, prime):

    for index in range(prime * prime, len(bool_list), prime):
        if bool_list[index] is False:
            continue

        bool_list[index] = False

    return bool_list

assert mark_false(list_true(6), 2) == [False, False, True, True, False, True, False]

def find_next(bool_list, index):
    while index + 1 < len(bool_list):
        index += 1

        if bool_list[index]:
            return index

    return None

assert find_next([True, True, True, True], 2) == 3
assert find_next([True, True, True, False], 2) is None

def prime_from_list(bool_list):
    return [index for index, boolean in enumerate(bool_list) if boolean]

assert prime_from_list([False, False, True, True, False]) == [2, 3]

def sieve(number):
    bool_list = list_true(number)
    prime = 2

    while prime is not None:
        bool_list = mark_false(bool_list, prime)
        prime = find_next(bool_list, prime)

    return prime_from_list(bool_list)

assert sieve(1000) == get_primes(0, 1000)

Обратите внимание, что bool - это класс Python, не используйте его в качестве имени переменной.

...