1. Что-то вроде доказательства от обратного: сначала предполагаем, что число простое
isPrime = true; А если находится число, деление на которое происходит нацело, то есть остаток от деления равен нулю
if((i%j) == 0), тогда доказано обратное, данное число составное:
isPrime = false;
2. Для того, чтоб не делать лишних итераций, если есть число N, то достаточно проверить только его делители от 2 до √N.
P.S. Если, поставить
i < 100, то в проверку пойдёт и само число, а так как число нацело делится само на себя, остаток будет 0 и условие сработает неправильно. Внутренний цикл перебирает делители числа, а для числа N, они находятся в диапазоне [1, N], однако так как и простые числа делятся на 1 и на самих себя, проверять нужно только диапазон (1, N).
Все делители больше чем √N дают в результате деления целые числа меньше чем √N, а так как меньшие числа мы уже перебрали, в проверке бо ́льших нет смысла. Условие
j<(i/j) как раз обеспечит перебор целых чисел в диапазоне [2, √N].
Можно также добавить небольшую оптимизацию:
for (j=2; j<(i/j); j++) {
if((i%j) == 0) {
isPrime = false;
break;
}
}
Если нашли один делитель, этого достаточно. Перебирать остальные не обязательно.
