Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

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

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

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

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

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

Проверить, является ли заданное число простым - C++
Дано целое число N (N>1). Проверить, является ли заданное число простым (простым называется число, имеющее ровно 2 делителя: себя и...

Проверить является ли введенное число простым - C++
Сделал программу. Считающую простые числа. По заданию мне нужно сделать их с помощь цикла while без for. можно использовать if else. Решил...

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

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

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

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

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

P.S. Здесь приведена реализация, правда только на Pacal (с ассеблером).
5
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 за интересные алгоритмы.
0
doctor_lecter
280 / 153 / 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.
0
Евгений 1994
0 / 0 / 0
Регистрация: 20.10.2012
Сообщений: 9
21.10.2012, 00:30 #12
спасибо весьма интересные виды алгоритмизации...в свободное время поиграюсь))
0
Thinker
Эксперт С++
4228 / 2202 / 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 и т.д. алгоритм был бы неверным
0
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;
}
1
Thinker
Эксперт С++
4228 / 2202 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
21.10.2012, 13:37 #15
Цитата Сообщение от NeRRouZ Посмотреть сообщение
Думаю так

Не по теме:

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

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

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

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

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

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


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

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

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