Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 143, средняя оценка - 4.71
ffantass
0 / 0 / 0
Регистрация: 06.10.2012
Сообщений: 30
20.10.2012, 18:11     Как проверить является ли число простым #1
Помогите пожалуйста!
Как проверить является ли число простым.
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.10.2012, 18:11     Как проверить является ли число простым
Посмотрите здесь:

является ли число простым C++
C++ в С++. как в стринггриде проверить является ли число простым?бегать нужно по столбцам
Найти среднее арифметичное для чисел пока не введем 0. Только через for и do-while и проверить является ли число простым C++
Проверка: является число простым C++
Функции. Проверить, простое число или нет. Увеличить его значение на натуральное число M. Проверить, осталось ли оно простым C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Евгений 1994
0 / 0 / 0
Регистрация: 20.10.2012
Сообщений: 9
20.10.2012, 21:55     Как проверить является ли число простым #2
лови...обращайся если что [задачи решаются на форуме]
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
 Аватар для doctor_lecter
279 / 152 / 8
Регистрация: 22.09.2012
Сообщений: 283
20.10.2012, 22:05     Как проверить является ли число простым #3
Цитата Сообщение от Евгений 1994 Посмотреть сообщение
l=l;
Зачем это?
И проверять достаточно пока делитель меньше чем корень из исходного числа
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
20.10.2012, 22:11     Как проверить является ли число простым #4
тут дело даже не в диапазоне, а сама программа в корне неверная. Например, все простые числа, начиная с 5, интерпретируются в результате как непростые. Правильно проверяются только числа 2 и 3, все остальные числа - "непростые"
Евгений 1994
0 / 0 / 0
Регистрация: 20.10.2012
Сообщений: 9
20.10.2012, 23:23     Как проверить является ли число простым #5
лови
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
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
20.10.2012, 23:27     Как проверить является ли число простым #6
Цитата Сообщение от Евгений 1994 Посмотреть сообщение
лови постаь лайк только ок?
это к кому фраза? программа опять неверная. числа 21, 35 и т.д. простыми считаются и таких чисел (неправильно определяемых) бесконечно много...
doctor_lecter
 Аватар для doctor_lecter
279 / 152 / 8
Регистрация: 22.09.2012
Сообщений: 283
21.10.2012, 00:07     Как проверить является ли число простым #7
Евгений 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
0 / 0 / 0
Регистрация: 20.10.2012
Сообщений: 9
21.10.2012, 00:15     Как проверить является ли число простым #8
прокоментируйте пожалуйста вши дествия
Цитата Сообщение от 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
 Аватар для AnyOne697
134 / 106 / 5
Регистрация: 22.05.2010
Сообщений: 532
21.10.2012, 00:17     Как проверить является ли число простым #9
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Нет, я, конечно, получу много башмаков по башке за эту ссылку, но не могу её не запостить сюда, хотя бы ради общего развития.

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

P.S. Здесь приведена реализация, правда только на Pacal (с ассеблером).
polyaKIDze
63 / 63 / 12
Регистрация: 16.07.2012
Сообщений: 147
21.10.2012, 00:20     Как проверить является ли число простым #10
http://ru.wikipedia.org/wiki/%D0%A0%...B5%D0%BD%D0%B0
ffantass, пользуйтесь википедией. вам предложен тупой перебор, хотя я даже не разбирался, что там напысано.

Либо выше алгоритм классный. Он вообще полиномиальный. И раз кнопки нет, хочется просто сказать спасибо AnyOne697 за интересные алгоритмы.
doctor_lecter
 Аватар для doctor_lecter
279 / 152 / 8
Регистрация: 22.09.2012
Сообщений: 283
21.10.2012, 00:24     Как проверить является ли число простым #11
Евгений 1994,
Искать делители числа имеет смысл только пока делитель меньше корня этого числа (дальше делители будут повторяться)
Потом для всех натуральных чисел от 2 и меньших корня проверяется остаток от деления n на i. Если остаток равен 0 ,то n делится нацело на i. В этом случае выводится "Не простое" и функция main завершается. Если проверены все i, и не нашлось таких чисел что n%i == 0, то выводится сообщение "Простое".
Еще у меня нигде не рассмотрен особый случай n == 1 и n <= 0.
Евгений 1994
0 / 0 / 0
Регистрация: 20.10.2012
Сообщений: 9
21.10.2012, 00:30     Как проверить является ли число простым #12
спасибо весьма интересные виды алгоритмизации...в свободное время поиграюсь))
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
21.10.2012, 10:25     Как проверить является ли число простым #13
AnyOne697, алгоритмы хорошие и известные, никто не спорит, просто они вероятностные. Если целью является проверить относительно небольшое целое число, то лучше использовать детерминированный алгоритм.

Добавлено через 5 минут
Цитата Сообщение от doctor_lecter Посмотреть сообщение
Искать делители числа имеет смысл только пока делитель меньше корня этого числа
если немного точнее, то меньше или равно, так как для чисел 2*2, 3*3, 5*5, 7*7 и т.д. алгоритм был бы неверным
NeRRouZ
 Аватар для NeRRouZ
4 / 4 / 0
Регистрация: 19.12.2010
Сообщений: 54
21.10.2012, 13:22     Как проверить является ли число простым #14
Думаю так
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
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
21.10.2012, 13:37     Как проверить является ли число простым #15
Цитата Сообщение от NeRRouZ Посмотреть сообщение
Думаю так

Не по теме:

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

AnyOne697
 Аватар для AnyOne697
134 / 106 / 5
Регистрация: 22.05.2010
Сообщений: 532
21.10.2012, 23:33     Как проверить является ли число простым #16
Thinker, второй алгоритм AKS - детерменизорован. Советую проверять, прежде чем писать.

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

Не по теме:

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

Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
22.10.2012, 09:11     Как проверить является ли число простым #17
Цитата Сообщение от AnyOne697 Посмотреть сообщение
второй алгоритм AKS - детерменизорован. Советую проверять, прежде чем писать

Не по теме:

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

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

AnyOne697
 Аватар для AnyOne697
134 / 106 / 5
Регистрация: 22.05.2010
Сообщений: 532
28.10.2012, 16:23     Как проверить является ли число простым #18
Цитата Сообщение от Thinker Посмотреть сообщение

Не по теме:

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

Не по теме:

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

RustamFly
16 / 2 / 0
Регистрация: 19.03.2015
Сообщений: 15
21.03.2015, 13:20     Как проверить является ли число простым #19
Число называется простым, если оно делится без остатка только на себя и на единицу.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.03.2015, 15:26     Как проверить является ли число простым
Еще ссылки по теме:

Проверить, является ли заданное число простым C++
C++ Проверить, является ли число простым

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
MicM
21.03.2015, 15:26     Как проверить является ли число простым
  #20

Не по теме:

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

Yandex
Объявления
21.03.2015, 15:26     Как проверить является ли число простым
Ответ Создать тему
Опции темы

Текущее время: 21:22. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru