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

@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 до корня исследуемого числа

Новые блоги и статьи Все статьи Все блоги /
Загрузка PNG-файла с альфа-каналом с помощью библиотеки SDL3_image на Android 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .	Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .
Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом

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

	Проверка числа на простоту 13.09.2012, 20:47. Показов 6338. Ответов 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