Проблема с пониманием алгоритма нахождения простых чисел?

Question

[Денис Каракчиев]

Задачка из книги Schildt- a beginner's guide - написать программку, находящую простые числа от 2-х до 100.
Ответ:

int i, j;
 boolean isPrime;

    for(i=2; i<100; i++) {
      isPrime = true;

      for (j=2; j<(i/j); j++) {
        if((i%j) == 0) isPrime = false;
      }

      if(isPrime) {
        System.out.println(i + " is prime");
      }
}

Код рабочий, но мне совершенно непонятны несколько вещей:
1. Почему вначале мы объявляем
isPrime = true;
но на выходе получается, если остаток от деления 0, то число простое, при этом isPrime в цикле становится false?
2. Почему во втором цикле j<(i/j), почему просто не создать j<100, ведь по сути нужно поделить числа на 1 и самих на себя без остатка? На 1 делится потому как переменная int, на себя без остатка, потому как i%j. Не понимаю этот момент ни в какую, и ведь если задать j<100, работать наотрез отказывается =)

Заранее спасибо ответившим и пояснившим.

П.с. До этого программированием не занимался, вышка совершенно не по профилю.

Answer 1

[Alexander Movchan]

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;
        }
      }

Если нашли один делитель, этого достаточно. Перебирать остальные не обязательно.

Comments

[Денис Каракчиев]

Ага, т.е. второй цикл осуществляется n раз для КАЖДОГО числа из верхнего цикла? Туговато это до меня доходило)

[Денис Каракчиев]

На счет оптимизации да, логично, но в книге пока до break не дошло, стараюсь по порядку, так быстрее. А то в первой же задачке задался оптимизацией и усложнением, в итоге вместо 15-ти минут потратил около часа, было интересно, но долго =)

[Alexander Movchan]

Денис Каракчиев: да, это вложенный цикл и он выполняется n раз для каждого раза внешнего цикла. Выходит так: перебираем все числа от 2 до 99, и для каждого этого числа перебираем все гипотетические делители.