Поиск простых чисел[поясните алгоритм]

[andrey95]

Здравствуйте!
В книжке нашел вот такую задачу на цикл while. Проверка является ли число введенное пользователем простым.

Код: [Выделить]

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
int n;
int i;
bool is_prime=true;
double root;
cout << "Enter a number and press ENTER: ";
cin>>n;
i=2;
root=sqrt(n);
while (i <= root)
{

if (n % i == 0)
{
is_prime=false;
break;
}
i++;
}
if(is_prime)
{
cout << "Number is prime." << endl;
}
else
{
cout<< "Number is not prime."<< endl;
}
return 0;
}
Поясните пожалуйста почему цикл продолжается до того момента пока счетчик не станет равен корню квадратному из введенного числа , а не самому этому числу.

[Mogidin]

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

возьмем 16
2 * 8
4 * 4
8 * 2

[andrey_p]

Ну ка попробую сформулировать, а то мне тут недавно сказали, что из программистов не получится математиков.

Если число d не является простым, значит оно равно произведению двух чисел - m * n, где m, n не равны 1. Предположим, что оба этих числа больше, чем корень из числа d - sqrt(d). Тогда m * n > sqrt(d) * sqrt(d) или m * n > d. Противоречие. Таким образом одно из этих чисел меньше или равно (в последнем случае m == n), sqrt(d). Итак, если перебирая числа от 2 до sqrt(d) включительно мы не находим множителя d, то заключаем, что d является простым.

Вот.  

[S_F_H]

Суть такая: простое число - число которое имеет только два делителя , т.е. делиться без остатков и дробей: само себя и единицу.

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


классическиий алгоритм:
Суть алгоритма в том, что проверяеться, делиться ли без остатка заданное число на числа в интервале от 2 до n / 2. если хоть на одном числе произошло деления, то число не являеться простым.

а root = sqrt(n) применяеться для уменьшения числа шагов, в предположении, что если число не имеет делителей среди чисел от 2-x до своего корня, то не будет иметь и до n/2. проверяеться методом индукции. сам перебрал около 100 простых чисел :-D