Памятка с генератором простых чисел

Question

У меня есть класс python, который генерирует n-е простое число, начиная с n-1-го простого числа и увеличивая его.Затем делится на все простые числа уже в списке до пола (sqrt (кандидат)).Но мой класс просто где-то попадает в бесконечные циклы, и я не могу понять, почему.

class prime_list():
    def __init__(self):
        self.primelst = [1]
        self.n = 1

    def increment(self):
        self.n+=1
        candidate = self.primelst[-1]+1
        limit = int(math.floor(math.sqrt(candidate)))
        prime = True
        while True:
            for p in self.primelst:
                if p>limit:
                    break
                if (candidate % p) == 0:
                    prime = False
                    break
            if prime:
                self.primelst.append(candidate)
                return
            else:
                candidate += 1
                limit = int(math.floor(math.sqrt(candidate)))
                prime = True

if __name__=="__main__":
    p = prime_list():
    p.increment()

Answer 1

Проблема в том, что вы ставите 1 в качестве начального значения в вашем простом списке. Затем функция increment ищет числа, не делимые на 1. Поскольку таких чисел нет, поиск ведется всегда.

Вы должны начать с 2 в качестве начального наименьшего простого числа или добавить специальный случай, обрабатывающий генерацию первого простого числа.

Answer 2

Некоторые примечания, в дополнение к исправлению, описанному другими:

• Вы не используете self.n и вам это не понадобится, поскольку списки Python знают их длину.
• Однако вы можете использовать некоторое кэширование для запоминания числа простых чисел для проверки , чтобы избежать сложных вычислений.
• primelst уродлив в качестве идентификатора: исключая случайные гласныекак это очень непитонический, и включение имени типа в имя идентификатора («список») противоречит духу типизации утки.Просто назовите контейнеры множественным числом.
• Предпочитайте короткие функции.Вычеркните простое обнаружение из логики добавления в список, и код станет значительно проще.Трудно проследить как разрывы, так и возвраты во вложенном цикле.
• Вы можете сделать основную функцию «приращения» генератором и получать доступ к простым числам по требованию, пока они генерируются.:)
• В стандартной библиотеке есть инструменты, которые можно использовать для упрощения (а) создания неограниченных циклов с подсчетом и (б) проверки каждого делителя в диапазоне.

Таким образом:

class prime_list():
    def __init__(self):
        self.primes = [2]
        self.to_use = 1


    def test(self, candidate):
        # Check if we need to expand the list of used primes.
        # Written a bit paranoid-ly
        while len(self.primes) > self.to_use:
            next = self.primes[self.to_use]
            # Note the mathematical rearrangement. :)
            if candidate <= next * next: self.to_use += 1
        # Test all the primes <= sqrt(candidate).
        return all(candidate % p != 0 for p in self.primes[:self.to_use])


    def __iter__(self):
        import itertools
        for candidate in itertools.count(3):
            if self.test(candidate):
                self.primes.append(candidate)
                yield candidate


if __name__ == "__main__":
    my_primes = prime_list()
    for p in my_primes:
        print "Generated:", p
        if p > 1000000: break
    print "Number of primes generated:", len(my_primes.primes)

Answer 3

Карл Кнехтель отвечает правильно, но вяло;проблема в том, что to_use продвигается слишком далеко и слишком рано.

Вот моя исправленная версия - я снял комментарии.

class prime_list():
    def __init__(self):
        self.primes = [2]
        self.to_use = 0


def test(self, candidate):
    next = self.primes[self.to_use]
    if candidate >= next * next:
      self.to_use += 1
      print candidate, next
    return all(candidate % p != 0 for p in self.primes[:self.to_use])


def __iter__(self):
    import itertools
    for candidate in itertools.count(3,2):
        if self.test(candidate):
            self.primes.append(candidate)
            yield candidate


if __name__ == "__main__":
    my_primes = prime_list()
#    print my_primes.primes[0]
    for p in my_primes:
        print "Generated:", p
        if p > 1000000: break
        sum += p
    print "Number of primes generated:", len(my_primes.primes)

Answer 4

Это не совсем вопрос языка или алгоритма, а отладочный :). Добавьте в свой цикл четыре оператора печати (по одному на каждую условную ветвь), и вы очень быстро поймете, почему ваша программа не заканчивается. Намного лучше выяснить, что происходит самостоятельно, с помощью расследования (научите кого-то ловить рыбу вместо того, чтобы давать ему рыбу ...).

Удачи!

Answer 5

Давайте сделаем пробежку:

// self.primelst = [1]
// self.n = 1

def increment(self):
        self.n+=1 // self.n = 2
        candidate = self.primelst[-1]+1 //candidate = 2
        limit = int(math.floor(math.sqrt(candidate))) // limit = 1
        prime = True // prime = True
        while True:
            for p in self.primelst: // p = 1
                if p>limit: // False
                    break // Does not go here
                if (candidate % p) == 0: // 2 % 1 == 0: True
                    prime = False // prime = False
                    break // breaks
            if prime: // False
                self.primelst.append(candidate) // Does not go here
                return // Does not return
            else: // Goes here
                candidate += 1 // candidate = 3
                limit = int(math.floor(math.sqrt(candidate))) // limit = 1
                prime = True // prime = True

Так что цикл while повторяется бесконечно. Алгоритм неверен.