Вывести все простые числа промежутка

Найти все простые числа на отрезке [a,b].

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Выведите все простые числа на отрезке [a, b]
Задание: » С клавиатуры вводятся два натуральных числа a и b. Выведите все простые числа на отрезке.

Вывести все простые числа на отрезке от А до В
Вводятся два числа A и В (A 10

на верхней границе в 400 000 принудительно снимается с выполнения, на 350 000 работает

но простота на этапе выполнения проверяется, слишком тривиально, чтобы выкладывать это)

Добавлено через 18 минут
впринципе это всё оптимизации поддаётся, в идеальном случае компилятор может и не вызывать конструкторов и забацать cout подряд один за другим, MVSC2010 почти так и сделал 17-23 он вывел в одном конструкторе

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

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

Найти все простые числа, меньше данного числа N. Определение простого числа описать в функции
Найти все простые числа, меньше данного числа N. Определение простого числа описать в функции

На отрезке [2, n] найти все натуральные числа, сумма цифр которых при умножении числа на а не изменится
Помогите,вот задание. На отрезке найти все натуральные числа, сумма цифр которых при умножении.

Источник

Как найти все простые числа из промежутка от a до b?

создать программу в методах

Даны натуральные числа от a до b (a 0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Найти все простые числа из промежутка от 1 до n
В чём тут проблема ? #include using namespace std; void prch(int n) < bool x =.

Получить все простые числа из промежутка
Написать програму, использую цикл for. Задача: Даны натуральные числа a, b (a 5

Ну понимаете, код я написала, но только не в методах, а мне нужно именно в методах.

Вот код и его нужно переделать

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

Добавлено через 1 минуту

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

Добавлено через 42 секунды
под первым спойлером Класс с методами, под вторым основной класс программы, с методом Main

Найти и распечатать в порядке убывания все простые числа из заданного промежутка, используя «решето Эратосфена»
Составить программу поиска и печати в порядке убывания все простые числа из промежутка (2..201).

Вывести на экран все простые числа из данного промежутка
Вывести на экран все простые числа из данного промежутка.

Вывести на экран все простые числа из данного промежутка
Здравствуйте, помогите пожалуйста с задачей Вывести на экран все простые числа из данного.

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

Источник

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

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

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

Помощь в написании контрольных, курсовых и дипломных работ здесь.

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

Найти все простые числа в заданном интервале
Добрый день. Задача следующая: ввести количество подсчётов (в задаче — cases). Потом столько же.

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

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

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

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

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

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

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

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

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

а как еще осуществить вывод на экран простых чисел по десяткам? все просты от 0 до 10 — в 1 строке, от 11 до 20 — во второй и так далее

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

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

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

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

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

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

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

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

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

Источник

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

Оптимизация алгоритма нахождения простых чисел

2 3 5 7 11 13 17 19 23 29 31… $250.000…

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

Алгоритм был придуман и тутже реализован на изучаемом языке. Программа запрашивала у пользователя число N и искала все простые числа до N включительно. После первого успешного теста сразу же возникло непреодолимое желание ввести N = «много». Программа работала, но не так быстро как хотелось бы. Естественно, дело было в многочисленных проверках (порядка N*N/2), поэтому пришлось избавиться от лишних. В итоге получилось 5 похожих алгоритмов каждый из которых работал быстре предыдущего. Недавно захотелось их вспомнить и реализовать, но на этот раз на Python.

Итак, поехали. Первый алгоритм, ударивший в студенческую голову, продемонстрирован в Листинге 1.

Очень быстро понимаешь, что в подсчете делителей каждого числа нет никакой надобности и поэтому переменную k можно освободить от своих обязанностей. Действительно, если хотябы один делитель имеется, то число уже не простое. Смотрим Листинг 2.

Конструкция break позволяет нам завершить выполнение внутреннего цикла и перейти к следующей итерации внешнего.
Далее возникает вопрос: «а зачем делить на 4, если на 2 число не делится?». Приходим к выводу, что искать делители нужно только среди простых чисел не превышающих делимое. Наш алгоритм превращается в… см. Листинг 3.

А потом вспоминаем теорию чисел и понимаем, что переберать надо только числа, не превосходящие корня из искомого. К примеру, если число M имеет делитель pi, то имеется делитель qi, такой, что pi * qi = M. То есть, чтобы найти пару, достаточно найти меньшее. Среди всех пар, предполагаемая пара с максимальным наименьшим — это пара с равными pi и qi, то есть pi * pi = M => pi = sqrt(M). Смотрим Листинг 4.

Код из Листинга 4 при N=10000 выполняется примерно в 1000 раз быстрее, чем самый первый вариант. Есть еще один «ускоритель», проверять только те числа, которые заканчиваются на 1, 3, 7 или 9 (так как остальные очевидно делятся на 2 или 5). Наблюдаем Листинг 5.

В следствии незначительного изменения Листинга 5 получаем небольшую прибавку в скорости:

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

P.S.
Благодаря замечаниям получаем Листинг 7:

при N=10000, поучаем время:
time 1 = 26.24
time 2 = 3.113
time 3 = 0.413
time 4 = 0.096
time 5 = 0.087
time 6 = 0.083
time 7 = 0.053

Результаты при n = 1 000 000:
time 7 = 7.088
time 8 = 1.143

Источник

Еще раз о поиске простых чисел

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

На снимке — скульптура абстрактного экспрессиониста Марка Ди Суверо «Решето Эратосфена», установленная в кампусе Стэнфорского университета

Введение

Напомним, что число называется простым, если оно имеет ровно два различных делителя: единицу и самого себя. Числа, имеющие большее число делителей, называются составными. Таким образом, если мы умеем раскладывать числа на множители, то мы умеем и проверять числа на простоту. Например, как-то так:
(Здесь и далее, если не оговорено иное, приводится JavaScript-подобный псевдокод)
Время работы такого теста, очевидно, есть O(n ½ ), т. е. растет экспоненциально относительно битовой длины n. Этот тест называется проверкой перебором делителей.

Довольно неожиданно, что существует ряд способов проверить простоту числа, не находя его делителей. Если полиномиальный алгоритм разложения на множители пока остается недостижимой мечтой (на чем и основана стойкость шифрования RSA), то разработанный в 2004 году тест на простоту AKS [1] отрабатывает за полиномиальное время. С различными эффективными тестами на простоту можно ознакомиться по [2].

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

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

Древнегреческий математик Эратосфен предложил следующий алгоритм для нахождения всех простых, не превосходящих данного числа n. Возьмем массив S длины n и заполним его единицами (пометим как невычеркнутые). Теперь будем последовательно просматривать элементы S[k], начиная с k = 2. Если S[k] = 1, то заполним нулями (вычеркнем или высеем) все последующие ячейки, номера которых кратны k. В результате получим массив, в котором ячейки содержат 1 тогда и только тогда, когда номер ячейки — простое число.

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

Еще немного операций можно сэкономить, если — по той же причине — начинать вычеркивать кратные k, начиная не с 2k, а с номера k 2 .

Реализация примет следующий вид:

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

Оценим сложность алгоритма. Первое вычеркивание требует n/2 действий, второе — n/3, третье — n/5 и т. д. По формуле Мертенса

так что для решета Эратосфена потребуется O(n log log n) операций. Потребление памяти же составит O(n).

Оптимизация и параллелизация

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

Более развитая оптимизация (т. н. wheel factorization) опирается на то, что все простые, кроме 2, 3 и 5, лежат в одной из восьми следующих арифметических прогрессий: 30k+1, 30k+7, 30k+11, 30k+13, 30k+17, 30k+19, 30k+23 и 30k+29. Чтобы найти все простые числа до n, вычислим предварительно (опять же при помощи решета) все простые до . Теперь составим восемь решет, в каждое из которых будут входить элементы соответствующей арифметической прогрессии, меньшие n, и высеем каждое из них в отдельном потоке. Все, можно пожинать плоды: мы не только понизили потребление памяти и нагрузку на процессор (в четыре раза по сравнению с базовым алгоритмом), но и распараллелили работу алгоритма.

Наращивая шаг прогрессии и количество решет (например, при шаге прогрессии 210 нам понадобится 48 решет, что сэкономит еще 4% ресурсов) параллельно росту n, удается увеличить скорость алгоритма в log log n раз.

Сегментация

Что же делать, если, несмотря на все наши ухищрения, оперативной памяти не хватает и алгоритм безбожно «свопится»? Можно заменить одно большое решето на последовательность маленьких ситечек и высевать каждое в отдельности. Как и выше, нам придется предварительно подготовить список простых до , что займет O(n ½-ε ) дополнительной памяти. Простые же, найденные в процессе высевание ситечек, нам хранить не нужно — будем сразу отдавать их в выходной поток.

Не надо делать ситечки слишком маленькими, меньше тех же O(n ½-ε ) элементов. Так вы ничего не выиграете в асимптотике потребления памяти, но из-за накладных расходов начнете все сильнее терять в производительности.

Решето Эратосфена и однострочники

На Хабрахабре ранее публиковалась большая подборка алгоритмов Эратосфена в одну строчку на разных языках программирования (однострочники №10). Интересно, что все они на самом деле решетом Эратосфена не являются и реализуют намного более медленные алгоритмы.

Дело в том, что фильтрация множества по условию (например, на Ruby) или использование генераторных списков aka list comprehensions (например, на Haskell) вызывают как раз то, избежать чего призван алгоритм решета, а именно поэлементную проверку делимости. В результате сложность алгоритма возрастает по крайней мере до (это число фильтраций), умноженного на (минимальное число элементов фильтруемого множества), где — число простых, не превосходящих n, т. е. до O(n 3/2-ε ) действий.

Однострочник на Scala ближе к алгоритму Эратосфена тем, что избегает проверки на делимость. Однако сложность построения разности множеств пропорциональна размеру большего из них, так что в результате получаются те же O(n 3/2-ε ) операций.

Вообще решето Эратосфена тяжело эффективно реализовать в рамках функциональной парадигмы неизменяемых переменных. В случае, если функциональный язык (например, OСaml) позволяет, стоит нарушить нормы и завести изменяемый массив. В [3] обсуждается, как грамотно реализовать решето Эратосфена на Haskell при помощи техники ленивых вычеркиваний.

Решето Эратосфена и PHP

Запишем алгоритм Эратосфена на PHP. Получится примерно следующее:

Вторая проблема: массивы в PHP ужасны по накладным расходам памяти. У меня на 64-битной системе каждый элемент $S из кода выше съедает по 128 байт. Как обсуждалось выше, необязательно держать сразу все решето в памяти, можно обрабатывать его порционно, но все равно такие расходы дóлжно признать недопустимыми.

Для решения этих проблем достаточно выбрать более подходящий тип данных — строку!

Теперь каждый элемент занимает ровно 1 байт, а время работы уменьшилось примерно втрое. Скрипт для измерения скорости.

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

В 1999 году Аткин и Бернштейн предложили новый метод высеивания составных чисел, получивший название решета Аткина. Он основан на следующей теореме.

Теорема. Пусть n — натуральное число, которое не делится ни на какой полный квадрат. Тогда

1. если n представимо в виде 4k+1, то оно просто тогда и только тогда, когда число натуральных решений уравнения 4x 2 +y 2 = n нечетно.
2. если n представимо в виде 6k+1, то оно просто тогда и только тогда, когда число натуральных решений уравнения 3x 2 +y 2 = n нечетно.
3. если n представимо в виде 12k-1, то оно просто тогда и только тогда, когда число натуральных решений уравнения 3x 2 −y 2 = n, для которых x >y, нечетно.

C доказательством можно ознакомиться в [4].

Из элементарной теории чисел следует, что все простые, большие 3, имеют вид 12k+1 (случай 1), 12k+5 (снова 1), 12k+7 (случай 2) или 12k+11 (случай 3).

Для инициализации алгоритма заполним решето S нулями. Теперь для каждой пары (x, y), где , инкрементируем значения в ячейках S[4x 2 +y 2 ], S[3x 2 +y 2 ], а также, если x > y, то и в S[3x 2 −y 2 ]. В конце вычислений номера ячеек вида 6k±1, содержащие нечетные числа, — это или простые, или делятся на квадраты простых.

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

Из описания видно, что сложность решета Аткина пропорциональна n, а не n log log n как у алгоритма Эратосфена.

Авторская, оптимизированная реализация на Си представлена в виде primegen, упрощенная версия — в Википедии. На Хабрахабре публиковалось решето Аткина на C#.

Как и в решете Эратосфена, при помощи wheel factorization и сегментации, можно снизить асимптотическую сложность в log log n раз, а потребление памяти — до O(n ½+o(1) ).

О логарифме логарифма

На самом деле множитель log log n растет крайне. медленно. Например, log log 10 10000 ≈ 10. Поэтому с практической точки зрения его можно полагать константой, а сложность алгоритма Эратосфена — линейной. Если только поиск простых не является ключевой функцией в вашем проекте, можно использовать базовый вариант решета Эратосфена (разве что сэкономьте на четных числах) и не комплексовать по этому поводу. Однако при поиске простых на больших интервалах (от 2 32 ) игра стоит свеч, оптимизации и решето Аткина могут ощутимо повысить производительность.

P. S. В комментариях напомнили про решето Сундарама. К сожалению, оно является лишь математической диковинкой и всегда уступает либо решетам Эратосфена и Аткина, либо проверке перебором делителей.

Источник