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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.77
lrf
0 / 0 / 0
Регистрация: 02.03.2014
Сообщений: 26
29.05.2014, 20:26     Проверка числа на простоту (нужны комментарии) #1
объясните пожалуйста, как в данной функции выполняется проверка числа на простоту. как можно поподробнее

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;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.05.2014, 20:26     Проверка числа на простоту (нужны комментарии)
Посмотрите здесь:

Проверка на простоту числа C++
Проверка числа на простоту C++
C++ Проверка числа на простоту
Быстрая проверка натурального числа на простоту C++
C++ Проверка числа на простоту
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
grikukan
61 / 61 / 21
Регистрация: 23.09.2012
Сообщений: 212
29.05.2014, 20:28     Проверка числа на простоту (нужны комментарии) #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Просто перебираем все числа от 2 до корня из проверяемого числа, и если проверяемое число делится на перебираемое, то оно не простое, а если не делится ни на одно - то составное...
lrf
0 / 0 / 0
Регистрация: 02.03.2014
Сообщений: 26
29.05.2014, 20:29  [ТС]     Проверка числа на простоту (нужны комментарии) #3
а почему до корня?
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). Противоречие.
Отсюда вывод: если у числа есть делители, то хотя один делитель меньше либо равен его корню.
Yandex
Объявления
29.05.2014, 20:34     Проверка числа на простоту (нужны комментарии)
Ответ Создать тему
Опции темы

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