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