Вывести простые числа python

Вывести простые числа python

Есть данный код:

Всё вроде бы ничего. НО почему-то туда попадает число:

Скрипт выводит 99 / 3 останавливается но добавляет 99 в множество.
В чем дело?

2 Answers

Заведите флаг, который останется включенным, если не нашлись делители:

<0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 131, 11, 137, 13, 139, 15, 143, 17,
257, 19, 269, 149, 271, 23, 151, 25, 277, 281, 283, 29, 157, 31, 289,
35, 163, 37, 293, 167, 41, 169, 43, 263, 173, 47, 49, 179, 53, 181,
59, 61, 191, 193, 67, 197, 71, 199, 73, 79, 83, 211, 89, 223, 97, 227,
101, 229, 103, 233, 107, 109, 239, 113, 241, 121, 251, 127>

Вместо флага можно использовать else ветку цикла:

Блог про алгоритмы и все что с ними связано. Основной инструмент реализации — Python.

суббота, 9 апреля 2011 г.

Простые числа

Просто́е число́ — это натуральное число, которое имеет ровно два различных натуральных делителя: единицу и самого себя. Все остальные числа, кроме единицы, называются составными.

Простые способы нахождения начального списка простых чисел вплоть до некоторого значения дают Решето Эратосфена, решето Сундарама и решето Аткина.

Решето́ Эратосфе́на — алгоритм нахождения всех простых чисел до некоторого целого числа n , который приписывают древнегреческому математику Эратосфену Киренскому.

Для нахождения всех простых чисел не больше заданного числа n, следуя методу Эратосфена, нужно выполнить следующие шаги:

  1. Выписать подряд все целые числа от двух до n (2, 3, 4, …, n).
  2. Пусть переменная p изначально равна двум — первому простому числу.
  3. Вычеркнуть из списка все числа от 2p до n, делящиеся на p (то есть, числа 2p, 3p, 4p, …)
  4. Найти первое не вычеркнутое число, большее чем p, и присвоить значению переменной p это число.
  5. Повторять шаги 3 и 4 до тех пор, пока p не станет больше, чем n
  6. Все не вычеркнутые числа в списке — простые числа.
Читайте также:  Почему падает фпс в world of tanks

На практике, алгоритм можно немного улучшить следующим образом. На шаге №3, числа можно вычеркивать, начиная сразу с числа p 2 , потому что все составные числа меньше его уже будут вычеркнуты к этому времени. И, соответственно, останавливать алгоритм можно, когда p 2 станет больше, чем n . Можно показать, что сложность алгоритма составляет O(nloglogn) операций в модели вычислений RAM, или O(n(logn)(loglogn)) битовых операций.

Еще один вариант исполнения я нашел на сайте http://www.intuit.ru/department/pl/python/2/5.html
Он основан на таком типе данных, как множество, а точнее на операции последовательного вычитания множеств.
Протестировав 2 этих метода, я получил следующие результаты:
При вычислении простых чисел до 650000, выигрывает алгоритм, оперирующий множествами. Потом, верх берет первый алгоритм. Видимо это связано с внутренней реализацией множеств в python. Если кто-то может описать поподробнее проблему, жду комментариев.

Алгоритм реализации: Решето Сундарама:

В математике решето́ Сундара́ма — детерминированный алгоритм нахождения всех простых чисел до некоторого целого числа . Разработан индийским студентом С. П. Сундарамом в 1934 году.

Обоснование: Алгоритм работает с нечётными натуральными числами большими единицы, представленными в виде 2m+1, где m является натуральным числом. Если число 2m+1 является составным, то оно представляется в виде произведения двух нечётных чисел больших единицы, то есть:
2m+1 = (2i+1)(2j+1) где i и j — натуральные числа, что также равносильно соотношению:
m = 2ij+i+j. Таким образом, если из ряда натуральных чисел исключить все числа вида 2ij + i + j , , то для каждого из оставшихся чисел m число 2m+1 обязано быть простым. И, наоборот, если число 2m+1 является простым, то число m невозможно представить в виде 2ij+i+j и, таким образом, m не будет исключено в процессе работы алгоритма.

Описание:
Из ряда натуральных чисел от 1 до N исключаются все числа вида
i + j + 2ij, где индексы пробегают все натуральные значения, для которых , а именно значения и Затем каждое из оставшихся чисел умножается на 2 и увеличивается на 1. Полученная в результате последовательность представляет собой все нечётные простые числа в отрезке [1, 2 N+1]. Особенно обратите внимание на то, что входной параметр N, а числа простые находим вплоть до 2N+1!

В математике решето́ А́ткина — быстрый современный алгоритм нахождения всех простых чисел до заданного целого числа N. Основная идея алгоритма состоит в использовании неприводимых квадратичных форм (представление чисел в виде a×x²+b×y²). Предыдущие алгоритмы в основном представляли собой различные модификации решета Эратосфена, где использовалось представление чисел в виде редуцированных форм (обычно прозведения x×y). Отдельный этап алгоритма вычеркивает числа, кратные квадратам простых чисел.

Как вы помните простое число — это такое число которое делится только на себя и на 1.
Никаких супер мега методик тут не будет. Я просто постараюсь на примере объяснить значение команды yield .

Читайте также:  Как в ворде посчитать количество символов

С начала напишем функцию, которая будет проверять простое это число или нет:

Думаю тут затруднений быть не должно.. Функция просто проверяет в цикле все числа от 2 до проверяемого и если хотя-бы 1 делится без остатка возвращает лож.
Следующей будет самая "интересная" функция этой статьи:

Эта функция генерирует простые числа. Мы в бесконечном цикле (не бойтесь это не повлияет на ресурсы, на самом деле в бесконечность интерпретатор не залезет) проверяем каждое число от 1 и если оно простое заносим его в результат при помощи yield . Эта команда по сути является чем-то вроде функции добавления значений в результат. Тут это неплохо показано на примере.
Ну и теперь используем єто всё:

Для каждого элемента (который мы назвали n) из числа который генерируется в primes(). И выводим все числа меньшие сотни.

Комментарии

Ваш код выдает не только простые числа, он выводит нечетные числа. Следует подправить первую функцию:
def isprime(n):
. if n == 1:
. return False
. for x in range(2, n):
. if n % x == 0:
. return False
. return True

Если я введу двойку то ответ будет Not prime (хотя это Prime). Почему нельзя прописать что если n == 2 то это Prime?

Ссылка на основную публикацию
Въехал в задний бампер какой штраф
Каждый владелец автомобиля хорошо знаком с правилами дорожного движения и наказаниями, однако, ГИБДД в последние годы очень активно начало менять...
Вода в раковине бьет током
Иногда случается так, что смеситель или стены в ванной вызывают неприятные ощущения. Чаще всего такие ощущения проявляются как легкие пощипывания...
Водный знак на фото программа
Добрый день, друзья. Какая лучшая программа для нанесения водяных знаков на фото и видео? Очень многие вебмастеры знают, что такое...
Выбивает пробки при включении чайника
0 27 февраля 2013 в 23:58:47 19552 Помните, что такое электрические пробки? Это плавкий предохранитель, который ставится на вводе электропитания...
Adblock detector