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

@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

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

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

	Как проверить является ли число простым 20.10.2012, 18:11. Показов 128821. Ответов 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

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

Решение