Поиск простых чисел?

Question

[Decoy_1]

Всем привет, помогите с программой по поиску простых чисел из учебника:

#include <iostream>
#include<conio.h>
using namespace std;

int main()
{
  int i, j;

  for (i = 2; i < 1000; i++){
    for (j = 2; j <= (i / j); j++){
      if (!(i % j)){
		  break;
		  }
    }
    if (j > (i / j)) cout << i << " - simple number\n";
  }
  _getch();
return 0;
}

Почему и для каких целей эти проверки:
for (j = 2; j <= (i / j); j++){ -- почему берется диапазон i/j

if (!(i % j)){

if (j > (i / j)) cout << i << " - simple number\n";

Answer 1

[longclaps]

Допустим i - составное, т.е. разлагается на p₁*p₂*..*p_n, тогда, чтобы удостовериться в том, что оно составное, достаточно найти его наименьший делитель (пусть это p₁).
Но он точно не больше произведения оставшихся делителей (p₂*..*p_n) == i / p₁ - вот и всё.

Answer 2

[Игорь]

Насчет диапазона longclaps написал правильно, объясню про остальное:
Этот блок кода:

if (!(i % j)){
    break;
}

проверяет, делится ли нацело i на j, если остаток от деления i % j равен 0, значит число i составное и перебирать остальные делители не имеет смысла, и внутренний цикл прерывается.
Условие if (j > (i / j)) проверяет, закончился ли полностью цикл перебора делителей, если j > (i / j) значит, что внутренний цикл не прерывался, а это значит что делителей для i не нашлось, и поэтому оно простое и i выводится на экран.