Как вывести простые числа c

Вычисление простых чисел на шаблонах C++

В этом посте я расскажу как сделать совершенно бесполезную вещь — вычислять простые числа при помощи шаблонов C++.

Алгоритмы проиллюстрированы кодом на Scheme, поэтому осторожно: скобочки!

Управляющие конструкции

Мы хотм получить compile-time аналог функции. В программировании на шаблонах в качестве функции выступает структура, параметры шаблона которой отвечают аргументам функции, а константные статические члены — результатам.

Аналогичный код на C++:

«Вызов» такой функции происходит через инстанцирование шаблона:

Шаблоны C++ позволяют обрабатывать некоторые значения параметров шаблона особым образом (специализация). Это позволяет организовать условную управляющую конструкцию:

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

Вычисление простых чисел

Постановка задачи

Мы хотим получить функцию, которая возвращает i-e простое число:

Проверка на простоту

Сразу такую функцию реализовать не получится, нужно начать с чего-то более простого. Проще всего проверить, является ли некоторое n простым числом. Для проверки проверяем, что остаток от деления n на все числа от n-1 до 1 не равен нулю.

Вопрос о том, считать ли 1 простым числом оставим открытым, но в данной реализации проверки 1 считается простым.

Нахождение следующего простого числа

Определим функцию, которая находит наименьшее простое число, большее заданного (то есть, следующее).

Нахождение просто числа по номеру

Что такое i-e простое число? Это следующее за (i-1)-м:

Источник

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

Найти все трехзначные простые числа. Определить функцию позволяющую распознавать простые числа
Найти все трехзначные простые числа. Определить функцию позволяющую распознавать простые числа.

Найти числа-близнецы: простые числа разность между которыми равна 2
Дано натуральное число n. Среди чисел n, n + 1, …, 2n найти все числа-близнецы: простые числа.

Найти простые числа с суммой цифр меньше заданного числа
нужно написать прогу, можно использовать только циклы. Если можно, с объяснениями. Условие: Найти.

Найти все натуральные числа, меньшие заданного числа и взаимно простые с ним
Дано натуральное число n. Необходимо получить все натуральные числа, меньшие nn и взаимно простые с.

Найти простые числа, которые можно разбить еще на два простых числа
Найти на промежутке количество простых чисел, которые можно разбить еще на два простых числа. К.

Найти сверхпростые числа: простые числа, номера которых являются простыми числами.
Привет родные форумчане! Пожалуйста помогите решить буду особенно благодарен если напишите код с.

Найти все простые числа меньшие заданного числа
Помогите Пожалуйста! Простое число это число которое делится только на 1 и на самого себя.

Источник

Алгоритмы поиска простых чисел в C#

Простое число — это целое положительное число, имеющее ровно два различных натуральных делителя — единицу и самого себя. Определение того является ли число простым или нет — это одна из самых распространенных задач, решаемых в рамках курса лабораторных работ по информатике. Ниже будет представлена реализация алгоритма поиска простых чисел в C#, а также использование различных циклов для вывода простых чисел.

Задача №1

Проверить является ли число простым и вывести результат вычисления в консоль.

Алгоритм определения простого числа

Для того, чтобы проверить является ли число N простым необходимо:

Реализация алгоритма определения простого числа в C#

Метод определения простого числа в C#, реализующий представленный выше алгоритм может быть представлен следующим образом:

Пример определения простых чисел из диапазона от 1 до N

Строго говоря, число 1 не является ни простым не составным, поэтому его можно было бы исключить из цикла, что мы и сделаем в следующем примере.

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

Задача поиска простых чисел может быть сформулирована и по другому, например, так: найти первые N простых чисел. В этом случае нам будет выгодно использовать цикл while:

Результатом работы программы будет вывод в консоль первых N простых чисел.

Итого

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

Источник

Вывести все простые числа в заданном интервале

Доброго времени суток!

Необходима Ваша помощь в написании программы на visual c++. Программы должна выводить все простые числа из заданного промежутка (начало и конец вводятся с клавиатуры) в виде
1 3 5 7
11 13 17 19
и так далее.

Получить все простые числа в заданном интервале
Пожалуйста помогите решить задачу, с++ вообще не понимаю, а сдавать надо. Даны натуральные числа a.

В заданном интервале натуральных чисел определить все простые числа
из заданного интервала натуральных чисел определить все простые числа

Вывести все числа Армстронга в заданном интервале
Здравствуйте, В универе дали задание: вывести все числа Армстронга в интервале ; Понимаю что это.

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

Комментарий модератора

Отправка во фриланс запрещена в тематических разделах

Алгоритм определения простого числа прост, обычно (сколько учебных пособий я пролистал в своих поисках нужных мне ответов) такое пишут почти в самом начале учебника

принцип прост это цикл который проверяет делимость нужного нам числа на числа от 2 до половины данного числа с ппомощью оператора «%»

Добавлено через 4 минуты
CyBOSSeR, аозьму за основу твой код. не сочти за плагиат.

всем большое спасибо)

условный оператор. если мне память не отшибло проверяем остаток от деления.

Добавлено через 43 секунды

Что за цикл по k? и для чего он тебе нужен?

Добавлено через 5 минут
ВО переделал свой код функции. жаль что сообщение свое подправить не могу, там ОШИБИЩА спс
CyBOSSeR, что помог.

Вывести все нечетные числа в заданном интервале
Кому не трудно помочь с вторым и третьим вопросом. Буду очень благодарен.Спасибо.

Вывести на консоль все числа Мерсена в заданном интервале
1. Вывести на консоль все числа Мерсена в заданном интервале. Числом Мерсена называется простое.

Найти все простые числа в заданном диапазоне и вывести их на экран
Доброго времени суток! Есть задачка, есть кривое решение. 🙂 Суть задачки такова: найти все.

Найти парные простые числа в заданном интервале
Помогите создать программу Составить программу: в интервале от a до b найти все парные простые.

Источник

Ищем простые числа до триллиона за тридцать минут

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

Сегодня я хотел бы поделиться с вами различными вариантами реализации поиска простых чисел на языке C#, начиная с классических алгоритмов — решета Эратосфена, Сундарама и Аткина, и кончая различными оптимизациями (сегментация, факторизация). Особый упор я делал на простоту: самый быстрый из алгоритмов, который мне удалось получить, содержит 120 строк кода и ищет простые числа до триллиона меньше, чем за 30 минут, а до миллиарда — меньше, чем за секунду (это далеко от производительности лучших из существующих библиотек по поиску простых чисел, но эти библиотеки обычно содержат свыше 4000 строк кода).
В заключение мы применим самую быструю реализацию для поиска максимального расстояния между двумя соседними простыми числами до триллиона. Прежде чем заходить под кат, я предлагаю вам попытаться угадать ответ. Для сравнения, для простых чисел до 100 максимальное растояние равно 8 (между соседними простыми числами 89 и 97), а до тысячи — 20 (между 887 и 907).

Весь исходный код можно найти на гитхабе.

1. Решето Эратосфена

Решето Эратосфена — самый простой и известный алгоритм для поиска простых чисел. Его суть состоит в следующем:

Поскольку наша задача — сравнить между собой разные реализации поиска простых чисел, мы наследуем все варианты от интерфейса ISieve, имеющего только один метод:

Для перечисления простых чисел был выбран способ колбеков, а не более привычные для C# энумераторы, поскольку он на 10-40% быстрее. Этот интерфейс позволяет единообразно тестировать разные реализации и сравнивать их между собой; в частности, мы будем считать количество, сумму и хеш простых чисел до миллиарда:

Алгоритм: решето Эратосфена
Ищет простые числа до миллиарда: 12.6 секунд.

2. Решето Сундарама

После этого, для оставшихся в списке чисел , последовательность чисел будет представлять все нечетные простые числа до N.

Заметим, что, в отличие от решета Эратосфена, алгоритм вычеркивает числа для любых комбинаций , поэтому его теоретическая сложность хуже: против . И действительно, на нашем тесте он работает медленней:

Алгоритм: решето Сундарама
Ищет простые числа до миллиарда: 18 секунд.

3. Решето Аткина

В 2003 году два профессора математики из Иллинойского университета в Чикаго Артур Аткин и Даниэль Бернштейн опубликовали статью, описывающую принципиально новый алгоритм поиска простых чисел, опирающийся на методы алгебраической теории чисел. Этот алгоритм теперь известен как решето Аткина. Его основная идея состоит в том, что существуют квадратичные формы для определенных классов , имеющие нечетное количество решений только когда — либо простое, либо имеет делитель . Это позволяет с помощью квадратичных форм отсеять все составные числа, не делящиеся на квадрат простого числа, а потом способом, аналогичным решету Эратосфена, отсеять кратные квадратам простых чисел.

Первый шаг имеет изящную реализацию на битовых массивах: значение квадратичной формы вычисляется для всех подходящих комбинаций , и соответствующий бит меняется на противоположный. Таким образом, если изначально все биты были установлены в 0, то в конце будут единичными только биты, переключенные нечетное количество раз, то есть биты для тех чисел , для которых соответствующая квадратичная форма имеет нечетное количество решений!

Практическая реализация рассматривает числа , не делящиеся на 2, 3, 5, и имеющие определенные остатки от деления на 60.

Этот алгоритм асимптотически быстрее, чем решето Эратосфена: против , но за счет большей сложности в практическом применении часто проигрывает решету Эратосфена при сравнимом количестве оптимизаций.

Алгоритм: решето Аткина

Ищет простые числа до миллиарда: 11.4 секунд.

4. Колёсная факторизация

Колёсная факторизация — вид оптимизации решета Эратосфена, позволяющий заранее исключить из рассмотрения числа, заведомо не являющиеся простыми. Например, любое простое число, большее 6, имеет остаток от деления на 6 либо 1, либо 5: или : при любых других остатках число будет делиться либо на 2, либо на 3. Аналогично, простое число, большее , может иметь только один из 8 остатков от деления на 30: . Еще одно преимущество оптимизации — уменьшение потребения памяти: вместо одного бита на число для решета Эратосфена или 0.5 бит на число для решета Сундарама, факторизация с базой требует примерно 0.27 бит на число, поскольку позволяет хранить 30 чисел в 8 битах. При аккуратном применении оптимизация позволяет ускорить просеивание в несколько раз, однако неоптимизированные варианты обычно работают медленно за счет большей сложности. В прошлой публикации я подробно описывал алгоритм, однако он не был оптимизирован по производительности, поэтому здесь я приведу более простой и эффективный вариант.

Алгоритм: (2,3,5)-факторизация
Ищет простые числа до миллиарда: 9.6 секунд.

5. Оптимизированное решето Эратосфена

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

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

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

Алгоритм: Оптимизированное решето Эратосфена
Ищет простые числа до миллиарда: 6.6 секунд.

6. Оптимизированное решето Сундарама

то есть, оно делает в точности то же самое, что и оптимизированное решето Эратосфена, только вычисления производятся над индексами битов, а не над самими числами. Поэтому сразу становится видно различие: решето Эратосфена вычеркивает только числа, кратные простым, а решето Сундарама — кратные всем числам! Очевидная оптимизация решета Сундарама — обрабатывать только те числа , для которых — простое число:

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

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

Алгоритм: Оптимизированное решето Сундарама
Ищет простые числа до миллиарда: 6.5 секунд.

7. Сегментированное решето Эратосфена

Все предыдущие алгоритмы хранили весь результат в памяти, что ограничивает их применение небольшими диапазонами. Например, при поиске простых чисел до триллиона, решето Эратосфена будет требовать 120 гигабайт оперативной памяти; кроме того, его скорость будет деградировать, так как просеивание (вычеркивание составных чисел) бегает по всему массиву, не эффективно используя кеши процессора.

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

вычеркиваем кратные 2: [ 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90]
вычеркиваем кратные 3: [ 81, 83, 85, 87, 89]
вычеркиваем кратные 5: [83, 85, 89]
вычеркиваем кратные 7 (нет в интервале): [83, 89]
Этот подход называется сегментированное решето, и с его применением требования к памяти снижаются с до . На практике размер интервалов выбирают либо равным , либо зависящим от размера кеша процессора.

За счет лучшего использования кеша алгоритм работает быстрее обычного решета Эратосфена на тех же данных:

Алгоритм: Сегментированное решето Эратосфена
Ищет простые числа до миллиарда: 8.6 секунд.

8. Оптимизированное сегментированное решето

Данная оптимизация относится к «народной» — она широко известна, но, похоже, не имеет своего названия. Цель оптимизации — избавиться от арифметического выражения, вычисляющего первое число в сегменте, кратное простому числу . Так как сегментированное решето обрабатывает сегменты подряд в порядке возрастания, нетрудно убедиться, что нужное число будет равно первому числу, кратному , выхожящему за граниы предыдущего сегмента. Таким образом, нам достаточно для каждого простого числа хранить текущее кратное ему число. В упрощенном виде это можно представить так:

Полная реализация с небольшими дополнительными оптимизациями позволяет ускорить предыдущий алгоритм примерно на 20%

Алгоритм: Оптимизированное сегментированное решето
Ищет простые числа до миллиарда: 7.1 секунд.

9. Сегментированная факторизация с базой 2

Раньше мы рассматривали оптимзацию, позволяющую хранить только нечетные числа, и ничего нам не мешает применить ее к предыдущему алгоритму. Только теперь массив PrimeMultiples будет хранить не , а :

Интересно, что основной цикл исключения составных чисел не изменился, разница только в инициализации массива PrimeMultiples и в преобразовании индекса битов в число по знакомой нам формуле .

Эта оптимизация ускоряет поиск простых чисел больще, чем вдвое:

Алгоритм: Сегментированная факторизация с базой 2
Ищет простые числа до миллиарда: 3.4 секунды.

10. Сегментированная (2,3)-факторизация

В предыдущей реализации мы исключили из рассмотрения числа, делящиеся на два; теперь исключим числа, делящиеся на 2 и 3. Тогда оставшиеся числа делятся на два класса: дающие 1 или 5 в остатке от деления на 6. Поэтому вместо одного битового массива используем два: PrimeMultiples_6kPlus1 и PrimeMultiples_6kPlus5; они будут хранить числа вида и для чисел, кратных , имеющих 1 или 5 в остатке от деления на 6. Дополнительные усилия нужны, чтобы найти первое число вида , имеющее нужный остаток от деления на 6, но это решается простым перебором .

Алгоритм: Сегментированная (2,3)-факторизация
Ищет простые числа до миллиарда: 2.6 секунды.

11. Сегментированная (2,3,5)-факторизация

Применим ту же идею для чисел, не делящихся на 2, 3 и 5. Тогда у нас будет не два битовых массива, а восемь, по одному на каждый остаток от деления на 30: . В остальном код не особо изменится, и даст нам еще небольшое ускорение.

Алгоритм: Сегментированная (2,3,5)-факторизация
Ищет простые числа до миллиарда: 2.3 секунды.

12. Оптимизированная сегментированная (2,3,5)-факторизация

Факторизация позволяет уменьшить количество чисел, которые мы вычеркиваем, но вычисление индекса байта и бита в битовом массиве (как при просеивании, так и при повторном проходе по массиву для перечисления простых чисел) все равно занимает большую часть времени. Поэтому воспользуемся уже знакомым нам трюком, пользуясь тем, что в факторизации с базой (2,3,5) восемь остатков: вместо восьми битовых массивов используем один массив байт, в котором каждый из восьми бит отвечает за свой остаток от деления на 30. Это позволит нам в массиве PrimeMultiples держать индекс байта, а индекс бита будет постоянным. Тогда внутренний цикл просеивания становится исключительно простым:

При таком подходе повторный проход по массиву уже занимает больше времени, поскольку требует больше битовых операций. Однако любой байт может принимать всего 256 вариантов, поэтому мы можем заранее вычислить все 256 комбинаций остатков, и вообще избавиться от битовых операций. Например:

Тогда получение простых чисел сводится к простому циклу:

Эта оптимизация ускоряет предыдущую реализацию больше, чем в два раза, позволяя найти простые числа до миллиарда меньше, чем за секунду!

Алгоритм: Оптимизированная сегментированная (2,3,5)-факторизация
Ищет простые числа до миллиарда: 0.93 секунды.

Максимальное расстояние между простыми числами до триллиона

Используя последнюю версию алгоритма, легко написать простой код, сканирующий простые числа до триллиона и ищущий максимальное расстояние между соседними простыми числами:

Результат работы программы:

Простые числа до 1,000,000,000,000
Время работы: 26 минут 30 секунд
Максимальное расстояние между простыми числами: 540
между 738,832,927,927 и 738,832,928,467

Лучшие библиотеки

Рассказ был бы не полон без сравнения с лучшими из существующих библиотек по поиску простых чисел.

Самая известная библиотека — primegen, основанная на сильно оптимизированном решете Аткина. Она написана на C самим Даниэлем Бернштейном (соавтором Аткина) 20 лет назад и оптимизирована под Пентиум, поэтому для эффективного ее использования требуется поменять размер буфера в файле conf-words:

На моем ноутбуке наилучшая производительность достигается при установке буфера 65536 байт. В библиотеку входит утилита primegaps, которая как раз и ищет максимальное расстояние между простыми числами. Время ее работы для простых чисел до триллиона — 19 минут.

Но на данный момент, пожалуй, самая быстрая библиотека — primesieve, написанная на c++ и включающая огромное количество оптимизаций, включая различные стратегии просеивания для маленьких, средних и больших простых чисел, автоматическое определение размера кешей процессора и многопоточность. На моем ноутбуке программа ищет простые числа до триллиона в 8 потоков за 70 секунд. Автор библиотеки Kim Walish подробно описывает оптимизации в коде, поэтому эта библиотека отлично подходит для изучения самых лучших на сегодняшний день оптимизаций и для практического применения.

Сводная таблица с результатами

Время поиска простых чисел до миллиарда, секунд.

Источник