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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.77
lrf
0 / 0 / 0
Регистрация: 02.03.2014
Сообщений: 26
#1

Проверка числа на простоту (нужны комментарии) - C++

29.05.2014, 20:26. Просмотров 1865. Ответов 3
Метки нет (Все метки)

объясните пожалуйста, как в данной функции выполняется проверка числа на простоту. как можно поподробнее

C++
1
2
3
4
5
6
7
8
9
bool Prime(int const num)// проверка числа на простоту
{
    for(int i = 2; i <= static_cast<int>(sqrt(num)); ++i)
    {
        if(num % i == 0)
            return false;
    }
    return 1 != num;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.05.2014, 20:26
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Проверка числа на простоту (нужны комментарии) (C++):

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

Проверка на простоту числа - C++
как мне сделать так, чтобы узнать простое является число или составное, не через bool, а как-нибудь через оператор switch case: т е, case...

Проверка числа на простоту - C++
Помогите написать программу которая проверяет простое число или нет.

Проверка числа на простоту - C++
Дано натуральное число n&gt;1. Проверьте, является ли оно простым. Программа должна вывести слово YES, если число простое и NO, если число...

Проверка числа на простоту - C++
Помогите решить 2 задачки, пожалуйста, 1. Написать программу для проверки натурального числа N на простоту. N вводится с клавиатуры. ...

Проверка числа на простоту - C++
Дано натуральное число N, проверить, простое оно или нет. Увеличить его значение на натуральное число M. Проверить, осталось ли оно ...

3
grikukan
61 / 61 / 21
Регистрация: 23.09.2012
Сообщений: 212
29.05.2014, 20:28 #2
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Просто перебираем все числа от 2 до корня из проверяемого числа, и если проверяемое число делится на перебираемое, то оно не простое, а если не делится ни на одно - то составное...
1
lrf
0 / 0 / 0
Регистрация: 02.03.2014
Сообщений: 26
29.05.2014, 20:29  [ТС] #3
а почему до корня?
0
grikukan
61 / 61 / 21
Регистрация: 23.09.2012
Сообщений: 212
29.05.2014, 20:34 #4
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Это легко доказать.
Пусть у числа n все делители больше его корня. Рассмотри один из делителей - p (p>sqrt(n)), тогда q=n/p;
Мы знаем, что sqrt(n)*sqrt(n)=n и что p*q=n. Но если p>sqrt(n) по допущению, то q<sqrt(n). Противоречие.
Отсюда вывод: если у числа есть делители, то хотя один делитель меньше либо равен его корню.
1
29.05.2014, 20:34
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.05.2014, 20:34
Привет! Вот еще темы с ответами:

Проверка числа на простоту - C++
Написать программу, которая запрашивает массив натуральных чисел (ввод с клавиатуры), а затем выводит на экран те элементы массива, которые...

Проверка числа на простоту - C++
Почему, если необ. проверить, является ли число простым(напр. ч-ло n),можно просматривать делители не от 2 до n, а от 2 до sqrt(n)? P.S....

Быстрая проверка натурального числа на простоту - C++
Часто возникает задача проверки натурального числа на простоту. При этом имеются вероятностные и детерминированные методы проверки. Здесь...

Робота с динамической памятью, проверка числа на простоту - C++
В динамическую память последовательно занести введенные с клавиатуры целые числа (признак завершения ввода - число ноль). Проверить все...


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

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

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