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

@AlexeyFo · Регистрация: 13.09.2012

Студворк — интернет-сервис помощи студентам

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

@soon · 13.09.2012, 20:57

Внизу страницы блок "Похожие темы"

@raz0rblade · 13.09.2012, 21:15

FOR'ом перебери все числа, до корня из этого числа!! Если ни на одно из них число не делится, значит оно простое.

@bz_ · 13.09.2012, 23:44

C++
1
2
3
4
5
6
7
8
9
10
11
int x;
cin >> x;
int *sum = new int;
sum = 0;
for (int i = 1; i <= x; i++){
    if (x % i == 0)
        sum++;
}
if (*sum == 2) cout << "Простое";
else cout << "Не простое";
delete sum;

@Thinker · 14.09.2012, 09:21

Сообщение от bz_

C++
1
2
3
4
for (int i = 1; i <= x; i++){
    if (x % i == 0)
        sum++;
}

Не по теме:

какой у вас затратный алгоритм сложностью O(n). поэкспериментируйте с 10-15 значными числами (в 10-ой системе счисления). можно же со сложностью $https://www.cyberforum.ru/cgi-bin/latex.cgi?O(\sqrt{n})$ сделать), о чем raz0rblade и говорит. хотя можно еще лучше придумать (речь не о вероятностных алгоритмах)

@Borkot · 14.09.2012, 09:36

Хорошо а в какую сторону копать нужно,что бы алгоритм проверял на простоту 10-15 значные числа быстро?

@Thinker · 14.09.2012, 09:42

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

Новые блоги и статьи Все статьи Все блоги /
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .

@AlexeyFo 0 / 0 / 0 Регистрация: 13.09.2012 Сообщений: 19

	Проверка числа на простоту 13.09.2012, 20:47. Показов 6363. Ответов 6 Метки нет (Все метки) Помогите написать программу которая проверяет простое число или нет. 0

@soon 2554 / 1319 / 178 Регистрация: 09.05.2011 Сообщений: 3,086 Записей в блоге: 1
	13.09.2012, 20:57
	Внизу страницы блок "Похожие темы" 0

@raz0rblade 55 / 55 / 2 Регистрация: 30.05.2012 Сообщений: 233 Записей в блоге: 1
	13.09.2012, 21:15
	FOR'ом перебери все числа, до корня из этого числа!! Если ни на одно из них число не делится, значит оно простое. 0

@Borkot 4 / 4 / 2 Регистрация: 05.05.2012 Сообщений: 201 Записей в блоге: 1
	14.09.2012, 09:36
	Хорошо а в какую сторону копать нужно,что бы алгоритм проверял на простоту 10-15 значные числа быстро? 0

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	14.09.2012, 09:42
	Во первых, можно использовать вероятностные алгоритмы, например алгоритм Рабина-Миллера. А если речь не о вероятностных алгоритмах, то можно очень сильно оптимизировать алгоритм, который пробегает числа от 2 до корня исследуемого числа 1