Питон как в списке найти простые числа
Перейти к содержимому

Питон как в списке найти простые числа

  • автор:

Решето Эратосфена — алгоритм определения простых чисел

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

Чтобы понять данный алгоритм, вспомним, что числа являются простыми, если делятся только на единицу и самих себя. Первое простое число — это 2, второе простое число — это 3. Теперь начнем рассуждать:

  1. Все четные числа, кроме двойки, — составные, т. е. не являются простыми, так как делятся не только на себя и единицу, а также еще на 2.
  2. Все числа кратные трем, кроме самой тройки, — составные, так как делятся не только на самих себя и единицу, а также еще на 3.
  3. Число 4 уже выбыло из игры, так как делится на 2.
  4. Число 5 простое, так как его не делит ни один простой делитель, стоящий до него.
  5. Если число не делится ни на одно простое число, стоящее до него, значит оно не будет делиться ни на одно сложное число, стоящее до него.

Последний пункт вытекает из того, что сложные числа всегда можно представить как произведение простых. Поэтому если одно сложное число делится на другое сложное, то первое должно делиться на делители второго. Например, 12 делится на 6, делителями которого являются 2 и 3. Число 12 делится и на 2, и на 3.

Алгоритм Эратосфена как раз заключается в последовательной проверке делимости чисел на предстоящие простые числа. Сначала берется первое простое и из ряда натуральных чисел высеиваются все кратные ему. Затем берется следующее простое и отсеиваются все кратные ему и так далее.

При реализации алгоритма Эратосфена на языке программирования есть некоторая сложность. Допустим, мы помещаем натуральные числа до заданного числа N в массив. Далее в процессе выполнения алгоритма будем заменять обнаруженные сложные числа нулями. После выполнения алгоритма те ячейки массива, которые не содержат нули, содержат простые числа, которые выводятся на экран.

Однако индексация массива начинается с нуля, а простые числа начинаются с двойки. Эта проблема решаема, но добавляет сложности в код. Поскольку алгоритм Эратосфена не такой уж простой, легче пренебречь началом и взять массив от 0 до N . Здесь важнее индексы, чем значения элементов. Значениями могут быть логические True , обозначающее простое число, и False , обозначающее сложное число.

В данном примере реализации алгоритма Эратосфена на языке программирования Python список заполняется числами от 0 до N включительно так, что индексы элементов совпадают с их значениями. Далее все непростые числа заменяются нулями:

Решето Эратосфена в Python

Решето Эратосфена в Python

Статьи

Введение

В ходе статьи используя алгоритм “Решето Эратосфена” найдём все простые числа до заданного числа N в Python.

Решето Эратосфена – это алгоритм нахождения всех простых чисел в диапазоне от 0, до заданного числа N.

Написание кода

Для начала дадим пользователю возможность ввода числа верхней границы диапазона:

Используя генератор заполним список значениями от одного, до заданного числа N:

Так как единица не является простым числом, заменим её на ноль:

Создадим переменную i равную двум, чтобы начать сразу с третьего элемента:

Создадим цикл, который не закончится, пока i <= n. Внутри цикла зададим условие, что если значение ячейки ранее не было обнулено, то в ней хранится простое число. Первое кратное ему число будет больше в два раза:

Далее внутри условия создадим ещё один цикл while, который не закончится, пока j <= n. Мы выявили, что данное число является составным, поэтому заменяем его нулём. Прибавляем i к j:

Преобразуем список в множество, после чего удалим все нули и выведем его:

Заключение

В ходе статьи мы с Вами научились использовать алгоритм “Решето Эратосфена” для нахождения всех простых чисел в заданном диапазоне и написали код на Python. Надеюсь Вам понравилась статья, желаю удачи и успехов! ��

Ищем простые числа в python — функции генераторы, yeld

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

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

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

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

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

Похожий код:

Программист, разработчик с 5 летним опытом работы. Учусь на разработчика игр на Unity и разработчика VR&AR реальности (виртуальной реальности). Основные языки программирования: C#, C++.

Бла, бла код

Ваш код выдает не только простые числа, он выводит нечетные числа. Следует подправить первую функцию:

….for x in range(2, n):

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

Вывести ряд простых чисел в python

Я пытаюсь изучить Python-программирование, и я довольно новичок в этом.

У меня возникали проблемы с печатью ряда простых чисел от одной до сотни. Я не могу понять, что не так с моим кодом.

Вот что я написал; он печатает все нечетные числа вместо простых чисел:

31 ответ

Вам нужно проверить все числа от 2 до n-1 (на самом деле до sqrt (n), но хорошо, пусть это будет n). Если n делится на любое из чисел, оно не простое. Если число простое, выведите его.

Вы можете написать то же самое намного короче и более питонично:

Как я уже сказал, было бы лучше проверять делители не от 2 до n-1, а от 2 до sqrt (n):

Для небольших чисел, таких как 101, это не имеет значения, но для 10 ** 8 разница будет очень большой.

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

Так как в первом цикле выбраны нечетные числа, во втором цикле нет необходимости проверять четные числа, поэтому значение ‘i’ можно начинать с 3 и пропускать до 2.

break завершает цикл, в котором он находится. Таким образом, вы только проверяете, делится ли он на 2, давая вам все нечетные числа.

что, как говорится, есть намного лучшие способы найти простые числа в python, чем это.

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

Начните с составления списка всех чисел от 2 до максимального желаемого числа n. Затем многократно принимайте наименьшее непересекающееся число и вычеркивайте все его кратные числа; числа, которые остаются непересекающимися, являются просторными.

Например, рассмотрите числа, меньшие 30. Сначала 2 обозначается как простой, затем 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28 и 30 являются вычеркнуто. Следующие 3 обозначены как простые, затем 6, 9, 12, 15, 18, 21, 24, 27 и 30 вычеркнуты. Следующий штрих равен 5, поэтому 10, 15, 20, 25 и 30 вычеркнуты. И так далее. Цифры остаются неизменными: 2, 3, 5, 7, 11, 13, 17, 19, 23 и 29.

Оптимизированная версия сита обрабатывает 2 отдельно и решает только нечетные числа. Кроме того, поскольку все композиты, меньшие квадрата текущего штриха, пересекаются меньшими штрихами, внутренний цикл может начинаться с p ^ 2 вместо p, а внешний цикл может останавливаться у квадратного корня n. Я оставлю оптимизированную версию для работы.

Я сторонник того, чтобы не принимать лучшее решение и не тестировать его. Ниже приведены некоторые изменения, которые я сделал для создания простых классов примеров, как с помощью @igor-chubin, так и с @user448810. Прежде всего позвольте мне сказать, что это отличная информация, спасибо вам, ребята. Но я должен признать @user448810 за его умное решение, которое оказалось самым быстрым на сегодняшний день (из тех, что я тестировал). Так тебе, сэр! Во всех примерах я использую значения 1 миллион (1 000 000) в виде n.

Пожалуйста, не стесняйтесь попробовать код.

Метод 1, как описано Игорем Чубиным:

Тест: Более 272 секунд

Метод 2, как описано Игорем Чубиным:

Тест: 73.3420000076 секунд

Метод 3, как описано Игорем Чубиным:

Тест: 11.3580000401 секунд

Метод 4, как описано Игорем Чубиным:

Тест: 8.7009999752 секунд

Метод 5, как описано user448810 (что я считал довольно умным):

Тест: 1.12000012398 секунд

Примечания: Решение 5, перечисленное выше (как было предложено user448810), оказалось самым быстрым и честно тихим творческим и умным. Я люблю это. Спасибо, ребята!

EDIT: О, и, кстати, я не чувствовал необходимости импортировать математическую библиотеку для квадратного корня из значения, поскольку эквивалент просто (n **. 5). В противном случае я не редактировал много других, а затем возвращал значения в массив и возвращал массив. Кроме того, было бы, вероятно, немного более эффективно хранить результаты в файле, чем подробные, и могло бы сэкономить много на памяти, если бы это было просто по одному, но стоило бы немного больше времени из-за записи на диск. Я думаю, что всегда есть место для улучшения. Так что, надеюсь, код имеет смысл парней.

Лучший способ решить указанную выше проблему — использовать алгоритм «Миллион Рабина». Он использует вероятностный подход, чтобы найти, является ли число простым или нет. И это самый эффективный алгоритм, с которым я столкнулся для этого.

Ниже приведен пример реализации python:

Функциональный модуль программы Python, который возвращает 1′-N простых чисел:

Мой способ перечисления простых чисел на номер записи без лишних хлопот использует свойство, которое позволяет получить любое число, которое не является простым с суммированием простых чисел.

Следовательно, если вы разделите номер записи со всеми штрихами ниже нее, и он не делится ни на один из них, вы знаете, что у вас есть простое.

Конечно, есть еще более быстрые способы получения простых чисел, но этот уже выполняется достаточно хорошо, особенно потому, что вы не делите номер записи на любое число, а довольно простые числа вплоть до этого числа.

С помощью этого кода мне удалось на моем компьютере перечислить все простые числа до 100 000 менее чем за 4 секунды.

Более простым и эффективным способом решения этой проблемы является сохранение всех найденных ранее простых чисел и проверка, является ли следующее число кратным любому из меньших простых чисел.

Обратите внимание, что any функция является функцией короткого замыкания, другими словами, она разорвет цикл, как только будет найдено истинное значение.

min = int (вход («Введите нижний диапазон:»)) max = int (вход («введите верхний диапазон:»))

print («Простые числа между», min, «и», max, «являются:»

для num в диапазоне (min, max + 1): если num> 1: для я в диапазоне (2, num): if (num% i) == 0: break else: print (num)

Сначала мы находим фактор этого числа

Скрипт для проверки премьер или нет

Скрипт для печати всех простых чисел до n

Вот самая простая логика для начинающих, чтобы получить простые числа:

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

Я был вдохновлен Игорем и сделал блок кода, который создает список:

Вот другой подход, который торгует пространство для более быстрого поиска. Это может быть быстрее всего.

Как насчет этого? Читая все предложения, я использовал это:

Основные номера до 1000000

78498

real 0m6.600s

пользователь 0m6.532s

sys 0m0.036s

Использование функции фильтра.

Это пример программы, которую я написал, чтобы проверить, является ли число простым или нет.

Вы заканчиваете цикл слишком рано. После того, как вы проверили все возможности в теле цикла for, а не сломались, число будет простым. Поскольку один не является простым, вам нужно начинать с 2:

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

Как вы можете видеть, нет необходимости вычислять квадратный корень, быстрее хранить квадрат для каждого простого числа и сравнивать каждый делитель с этим числом.

Здесь простая и интуитивно понятная версия проверки того, является ли это простым в функции RECURSIVE!:) (Я сделал это как домашнее задание для класса MIT) В python он работает очень быстро до 1900 года. Если вы попробуете более 1900, вы получите интересную ошибку:) (Хотелось бы узнать, сколько номеров может контролировать ваш компьютер?)

Конечно. если вам нравятся рекурсивные функции, этот небольшой код может быть обновлен со словарем, чтобы серьезно увеличить его производительность и избежать этой смешной ошибки. Здесь просто обновление уровня 1 с интеграцией MEMORY:

Вот резули, где я напечатал последние 100 простых чисел.

время и дата: 2013-10-15 13: 32: 11.674448

Есть 9594 простых чисел, до 100000

[99991, 99989, 99971, 99961, 99929, 99923, 99907, 99901, 99881, 99877, 99871, 99859, 99839, 99833, 99829, 99823, 99817, 99809, 99793, 99787, 99767, 99761, 99733, 99721, 99719, 99713, 99709, 99707, 99689, 99679, 99667, 99661, 99643, 99623, 99611, 99607, 99581, 99577, 99571, 99563, 99559, 99551, 99529, 99527, 99523, 99497, 99439, 99431, 99409, 99401, 99397, 99391, 99377, 99371, 99367, 99349, 99347, 99317, 99289, 99277, 99259, 99257, 99251, 99241, 99233, 99223, 99191, 99181, 99173, 99137, 99133, 99131, 99119, 99109, 99103, 99089, 99083, 99079, 99053, 99041, 99023, 99017, 99013, 98999, 98993, 98981, 98963, 98953, 98947, 98939, 98929, 98927, 98911, 98909, 98899, 98897].

Для его вычисления потребовался ваш компьютер 0: 00: 40.871083.

Так что для моего ноутбука i7 потребовалось 40 секунд, чтобы вычислить его.:)

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *