Как проверить является ли число простым

@ffantass · Регистрация: 06.10.2012

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

Помогите пожалуйста!
Как проверить является ли число простым.

@Евгений 1994 · 20.10.2012, 21:55

лови...обращайся если что [задачи решаются на форуме]

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# include <iostream>
# include <stdio.h>
 
void main(void)
{      float k; int l,n;
        l=0;
std::cout<<"ww chislo n=";
 std::cin>>n;
 
 
 
for(int i=2;i<n-1;i++){
 k=n/i;
if (k==int(k))
l=l+1;
else
l=l;
}
if (l>=1)
std::cout<<"chislo ne proste";
else
std::cout<<"chislo n="<<n<<" proste";
 
  getchar();getchar();
}

@doctor_lecter · 20.10.2012, 22:05

Сообщение от Евгений 1994

l=l;

Зачем это?
И проверять достаточно пока делитель меньше чем корень из исходного числа

@Thinker · 20.10.2012, 22:11

тут дело даже не в диапазоне, а сама программа в корне неверная. Например, все простые числа, начиная с 5, интерпретируются в результате как непростые. Правильно проверяются только числа 2 и 3, все остальные числа - "непростые"

@Евгений 1994 · 20.10.2012, 23:23

лови

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# include <iostream>
# include <stdio.h>
 
void main(void)
{      float k; int l,n;
        l=0;
std::cout<<"ww chislo n=";
 std::cin>>n;
 
 
 
for(int i=2;i<n;i++){
 k=n/i;    float f=k-int(k);
if (f>0 && f<0)
l=l+1;
else
l=l;
 
}
if (l>1)
std::cout<<"chislo ne proste";
else
std::cout<<"chislo n="<<n<<" proste";
 
  getchar();getchar();
}

@Thinker · 20.10.2012, 23:27

Сообщение от Евгений 1994

лови постаь лайк только ок?

это к кому фраза? программа опять неверная. числа 21, 35 и т.д. простыми считаются и таких чисел (неправильно определяемых) бесконечно много...

@doctor_lecter · 21.10.2012, 00:07

Евгений 1994, чего вы хотите добиться строчкой l=l ?
if (f>0 && f<0). Что это за новые числа, которые больше и меньше нуля одновременно?
И делится ли одно число на другое можно проверить по остатку от деления.

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <cmath>
#include <iostream>
#include <locale>
using namespace std;
int main() {
    setlocale(LC_ALL,"Russian");
    int n;
    cin >> n;
    float end = sqrt((float)n);
    for (int i=2; i <= end; ++i) {
        if (n%i == 0) {
            cout << "Не простое" << endl;
            return 0;
        }
    }
    cout << "Простое" << endl;
}

@Евгений 1994 · 21.10.2012, 00:15

прокоментируйте пожалуйста вши дествия

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

Евгений 1994, чего вы хотите добиться строчкой l=l ? И делится ли одно число на другое можно проверить по остатку от деления.

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <cmath>
#include <iostream>
#include <locale>
using namespace std;
int main() {
    setlocale(LC_ALL,"Russian");
    int n;
    cin >> n;
    float end = sqrt((float)n);
    for (int i=2; i <= end; ++i) {
        if (n%i == 0) {
            cout << "Не простое" << endl;
            return 0;
        }
    }
    cout << "Простое" << endl;
}

@AnyOne697 · 21.10.2012, 00:17

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

Так же, для общего развития следует знать про это.

P.S. Здесь приведена реализация, правда только на Pacal (с ассеблером).

@polyaKIDze · 21.10.2012, 00:20

http://ru.wikipedia.org/wiki/%... 0%BD%D0%B0
ffantass, пользуйтесь википедией. вам предложен тупой перебор, хотя я даже не разбирался, что там напысано.

Либо выше алгоритм классный. Он вообще полиномиальный. И раз кнопки нет, хочется просто сказать спасибо AnyOne697 за интересные алгоритмы.

@doctor_lecter · 21.10.2012, 00:24

Евгений 1994,
Искать делители числа имеет смысл только пока делитель меньше корня этого числа (дальше делители будут повторяться)
Потом для всех натуральных чисел от 2 и меньших корня проверяется остаток от деления n на i. Если остаток равен 0 ,то n делится нацело на i. В этом случае выводится "Не простое" и функция main завершается. Если проверены все i, и не нашлось таких чисел что n%i == 0, то выводится сообщение "Простое".
Еще у меня нигде не рассмотрен особый случай n == 1 и n <= 0.

@Евгений 1994 · 21.10.2012, 00:30

спасибо весьма интересные виды алгоритмизации...в свободное время поиграюсь))

@Thinker · 21.10.2012, 10:25

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

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

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

Искать делители числа имеет смысл только пока делитель меньше корня этого числа

если немного точнее, то меньше или равно, так как для чисел 2*2, 3*3, 5*5, 7*7 и т.д. алгоритм был бы неверным

@NeRRouZ · 21.10.2012, 13:22

Думаю так

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
 
int main()
{
     int n;  // число
     int d;  // делитель
     int r;  // остаток от деления n на d
 
     scanf("%d", &n);
     d = 2;        // сначала делим на 2
     do {
        r = n % d;
        if (r != 0) d++;
     }
     while ( r != 0 ); // пока n не разделится на d
     if (d == n)
       printf("%d - Prostoe" ,n);
     else  printf("%d - Ne prostoe" ,n);
 
   return 0;
}

@Thinker · 21.10.2012, 13:37

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

Думаю так

Не по теме:

ну да, для простого числа, состоящего из 8-10 десятичных цифр алгоритм придется как нельзя кстати

@AnyOne697 · 21.10.2012, 23:33

Thinker, второй алгоритм AKS - детерменизорован. Советую проверять, прежде чем писать.

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

Не по теме:

polyaKIDze, всегда пожалуйста

@Thinker · 22.10.2012, 09:11

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

второй алгоритм AKS - детерменизорован. Советую проверять, прежде чем писать

Не по теме:

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

P.S. Интересно, если AKS такой неплохой алгоритм, что же он не распространен...

@AnyOne697 · 28.10.2012, 16:23

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

Не по теме:

ну да, так и есть. посмотрел первую и третью ваши ссылки, вот и упустил, спасибо). вы бы хоть назвали по-человечески эти ссылки, было бы понятнее, а то тыкаться в каждую ссылку под названием "ссылка" не каждый будет. поэтому я, в свою очередь, советую вам называть ссылки со смыслом, если их несколько.
P.S. Интересно, если AKS такой неплохой алгоритм, что же он не распространен...

Не по теме:

Ну... Просто я накидал ссылок не Вам, а человеку, которому AKS ничего не скажет. Не сказало бы. Впрочем, и Вам вряд ли название что-нибудь сказало. Название ссылки как ссылка - просто чтобы не вставлять огромный адресс. Не более.
AKS распространён. В научной сфере. В пратике всё равно проще использовать модификации теста Миллера-Рабина, так как скорость выполнения значительная, а вероятность ошибки - малая. Очень малая. Впрочем, предполагаю, что в военной сфере используется именно AKS - лишняя доля процента расшифровки передачи важных данных совсем не то, чего они там добиваются.
В любых остальных случаях процессорное время стоит дороже.
И, конечно, ссылка.

@RustamFly · 21.03.2015, 13:20

Число называется простым, если оно делится без остатка только на себя и на единицу.

@MicM · 21.03.2015, 15:26

Не по теме:

Адмирал очевидность у штурвала! Вот археологи :D

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@ffantass 0 / 0 / 0 Регистрация: 06.10.2012 Сообщений: 30

	Как проверить является ли число простым 20.10.2012, 18:11. Показов 128454. Ответов 22 Метки нет (Все метки) Помогите пожалуйста! Как проверить является ли число простым. 0

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	20.10.2012, 22:11
	тут дело даже не в диапазоне, а сама программа в корне неверная. Например, все простые числа, начиная с 5, интерпретируются в результате как непростые. Правильно проверяются только числа 2 и 3, все остальные числа - "непростые" 1

@AnyOne697 134 / 106 / 10 Регистрация: 22.05.2010 Сообщений: 533
	21.10.2012, 00:17
	Сообщение было отмечено как решение Решение Нет, я, конечно, получу много башмаков по башке за эту ссылку, но не могу её не запостить сюда, хотя бы ради общего развития. Так же, для общего развития следует знать про это. P.S. Здесь приведена реализация, правда только на Pacal (с ассеблером). 5

@polyaKIDze 64 / 64 / 20 Регистрация: 16.07.2012 Сообщений: 147
	21.10.2012, 00:20
	http://ru.wikipedia.org/wiki/%... 0%BD%D0%B0 ffantass, пользуйтесь википедией. вам предложен тупой перебор, хотя я даже не разбирался, что там напысано. Либо выше алгоритм классный. Он вообще полиномиальный. И раз кнопки нет, хочется просто сказать спасибо AnyOne697 за интересные алгоритмы. 0

@doctor_lecter 284 / 157 / 30 Регистрация: 22.09.2012 Сообщений: 283
	21.10.2012, 00:24
	Евгений 1994, Искать делители числа имеет смысл только пока делитель меньше корня этого числа (дальше делители будут повторяться) Потом для всех натуральных чисел от 2 и меньших корня проверяется остаток от деления n на i. Если остаток равен 0 ,то n делится нацело на i. В этом случае выводится "Не простое" и функция main завершается. Если проверены все i, и не нашлось таких чисел что n%i == 0, то выводится сообщение "Простое". Еще у меня нигде не рассмотрен особый случай n == 1 и n <= 0. 0

@Евгений 1994 0 / 0 / 0 Регистрация: 20.10.2012 Сообщений: 9
	21.10.2012, 00:30
	спасибо весьма интересные виды алгоритмизации...в свободное время поиграюсь)) 0

@AnyOne697 134 / 106 / 10 Регистрация: 22.05.2010 Сообщений: 533
	21.10.2012, 23:33
	Thinker, второй алгоритм AKS - детерменизорован. Советую проверять, прежде чем писать. Добавлено через 1 минуту Не по теме: polyaKIDze, всегда пожалуйста 0

@RustamFly 16 / 2 / 0 Регистрация: 19.03.2015 Сообщений: 17
	21.03.2015, 13:20
	Число называется простым, если оно делится без остатка только на себя и на единицу. 0

@MicM
	21.03.2015, 15:26
	Не по теме: Адмирал очевидность у штурвала! Вот археологи :D 0

Как проверить является ли число простым

Решение