граница проверки простого числа

[fs444]

У Дейтлов есть задача:


Написал такой код:

#include<iostream>
using namespace std;

#include<windows>
#include<cmath>

void prostoeChislo(int chislo);

int main()
{
     double chislo; //число, которое проверяется, простое оно или нет. В.п.

//   cout << "Vvedite chislo: " << endl;
//   cin >> chislo;

//   for (chislo = 1; chislo <= sqrt(10000.0); chislo++)
   for (chislo = 1; chislo <= (10000/2); chislo++)
   {
      prostoeChislo(chislo);
   }

   system("pause");
   return 0;
}

void prostoeChislo(int chislo)
{
   int status = 1; // 1 - простое, 2 - непростое

   if (chislo == 1)
   {
      status = 2;
   }
   else
   {
      for (int i = 2; i < chislo; i++)
      {
         if (chislo % i == 0)
         {
            status = 2;
         }
      }
   }

   if (status == 1)
   {
      cout << "Chislo " << chislo << " prostoe" << endl;
   }
   else if (status == 2)
   {
//      cout << "Chislo " << chislo << " NE prostoe" << endl;
   }
}

Вот они пишут, что при использовании sqrt() производительность выше, чем при n/2. Так ведь 10000 / 2 = 5000, а sqrt(10000) = 100. Получается, часть чисел теряется. Так?

[Гром]

Если число n (sqrt(n) = m) делится на x > m, то y = n / x будет y < m. Соответственно, если число не простое, то существование делителя было найдено еще раньше, чем дошли до x.

[fs444]

А как понимать запись "n (sqrt(n) = m)"?

[Ozerich]

Короче, у числа N нету делителей, больше чем sqrt(N), т.е корень из N

[fs444]

Ага, ясно, спасибо.