Форум русскоязычного сообщества Ubuntu


Автор Тема: Поиск простых чисел[поясните алгоритм]  (Прочитано 714 раз)

0 Пользователей и 1 Гость просматривают эту тему.

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

  • Участник
  • *
  • Сообщений: 193
    • Просмотр профиля
    • Mogidin.Local.Blog
доходим до середины, а дальше будут повторы проверенного, только множители местами меняются.

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

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 является простым.

Вот.   8)
« Последнее редактирование: 19 Май 2011, 17:34:54 от andrey_p »

Оффлайн S_F_H

  • Участник
  • *
  • Сообщений: 129
  • Да будет crossplatform!
    • Просмотр профиля
Суть такая: простое число - число которое имеет только два делителя , т.е. делиться без остатков и дробей: само себя и единицу.

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


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

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

 

Страница сгенерирована за 0.164 секунд. Запросов: 24.