Satori_Kanzo
@Satori_Kanzo
Make code not war

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

Задачка из книги 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, работать наотрез отказывается =)

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

П.с. До этого программированием не занимался, вышка совершенно не по профилю.
  • Вопрос задан
  • 1857 просмотров
Решения вопроса 1
@Alexander1705
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;
        }
      }

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы