Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 143, средняя оценка - 4.71
ffantass
0 / 0 / 0
Регистрация: 06.10.2012
Сообщений: 30
#1

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

20.10.2012, 18:11. Просмотров 28550. Ответов 21
Метки нет (Все метки)

Помогите пожалуйста!
Как проверить является ли число простым.
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.10.2012, 18:11
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Как проверить является ли число простым (C++):

Проверить, является ли число простым
3. Проверить, является ли число простым. Ввести с клавиатуры

Проверить является ли заданное число простым
помогите плиз!) Дано натуральное число N, проверить простое оно или нет ....

Проверить является ли заданное число простым
Не знаю как написать программу. Только начал учить С++ и задали задачу:...

Проверить, является ли заданное число простым
Дано целое число N (N>1). Проверить, является ли заданное число простым...

Проверить является ли введенное число простым
Сделал программу. Считающую простые числа. По заданию мне нужно сделать их с...

Проверить, является ли заданное натуральное число простым
у меня есть алгоритм вывода простых чисел, как зделать так штоб можна было...

21
Евгений 1994
0 / 0 / 1
Регистрация: 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();
}
0
doctor_lecter
281 / 154 / 30
Регистрация: 22.09.2012
Сообщений: 283
20.10.2012, 22:05 #3
Цитата Сообщение от Евгений 1994 Посмотреть сообщение
l=l;
Зачем это?
И проверять достаточно пока делитель меньше чем корень из исходного числа
0
Thinker
Эксперт С++
4232 / 2206 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
20.10.2012, 22:11 #4
тут дело даже не в диапазоне, а сама программа в корне неверная. Например, все простые числа, начиная с 5, интерпретируются в результате как непростые. Правильно проверяются только числа 2 и 3, все остальные числа - "непростые"
1
Евгений 1994
0 / 0 / 1
Регистрация: 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();
}
0
Thinker
Эксперт С++
4232 / 2206 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
20.10.2012, 23:27 #6
Цитата Сообщение от Евгений 1994 Посмотреть сообщение
лови постаь лайк только ок?
это к кому фраза? программа опять неверная. числа 21, 35 и т.д. простыми считаются и таких чисел (неправильно определяемых) бесконечно много...
0
doctor_lecter
281 / 154 / 30
Регистрация: 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;
}
0
Евгений 1994
0 / 0 / 1
Регистрация: 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;
}
0
AnyOne697
134 / 106 / 10
Регистрация: 22.05.2010
Сообщений: 533
21.10.2012, 00:17 #9
Лучший ответ Сообщение было отмечено как решение

Решение

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

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

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

Либо выше алгоритм классный. Он вообще полиномиальный. И раз кнопки нет, хочется просто сказать спасибо AnyOne697 за интересные алгоритмы.
0
doctor_lecter
281 / 154 / 30
Регистрация: 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.
0
Евгений 1994
0 / 0 / 1
Регистрация: 20.10.2012
Сообщений: 9
21.10.2012, 00:30 #12
спасибо весьма интересные виды алгоритмизации...в свободное время поиграюсь))
0
Thinker
Эксперт С++
4232 / 2206 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
21.10.2012, 10:25 #13
AnyOne697, алгоритмы хорошие и известные, никто не спорит, просто они вероятностные. Если целью является проверить относительно небольшое целое число, то лучше использовать детерминированный алгоритм.

Добавлено через 5 минут
Цитата Сообщение от doctor_lecter Посмотреть сообщение
Искать делители числа имеет смысл только пока делитель меньше корня этого числа
если немного точнее, то меньше или равно, так как для чисел 2*2, 3*3, 5*5, 7*7 и т.д. алгоритм был бы неверным
0
NeRRouZ
4 / 4 / 8
Регистрация: 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;
}
1
Thinker
Эксперт С++
4232 / 2206 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
21.10.2012, 13:37 #15
Цитата Сообщение от NeRRouZ Посмотреть сообщение
Думаю так

Не по теме:

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

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

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

Не по теме:

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

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

Не по теме:

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

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

0
AnyOne697
134 / 106 / 10
Регистрация: 22.05.2010
Сообщений: 533
28.10.2012, 16:23 #18
Цитата Сообщение от Thinker Посмотреть сообщение

Не по теме:

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

Не по теме:

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

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

Не по теме:

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

0
21.03.2015, 15:26
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.03.2015, 15:26
Привет! Вот еще темы с ответами:

Проверить, является ли введенное с клавиатуры число простым
помогите составить программу в С++ с использованием цикла for Составить...

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

Найти среднее арифметичное для чисел пока не введем 0. Только через for и do-while и проверить является ли число простым
Помогите пожалуйста! Найти среднее арифметичное для чисел пока не введем...

Функции. Проверить, простое число или нет. Увеличить его значение на натуральное число M. Проверить, осталось ли оно простым
Помогите пожалуйста 1. Дано натуральное число N, проверить, простое оно или...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru