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

Question

Решаю задачи по списку задач Java. Есть условие в задачи:

Напишите программу, которая выводит на консоль простые числа в промежутке от [2, 100]. Используйте для решения этой задачи оператор "%" (остаток от деления) и циклы.

И решение этой задачи:

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

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

        if(isPrime){
            System.out.println(i);
        }
    }

Вопрос: Зачем использовать второй цикл и каждый раз заходить в него? почему сразу не сделать в первом цикле проверку i%2? т.е.:

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

            if(i % 2 == 0){
                isPrime = false;

        }

        if(isPrime){
            System.out.println(i);
        }
    }

Answer 1

Простые числа это те которые нацело делятся только на 1 и на само себя.

Например 2 - это простое число, т.к. оно делится на 1 и на 2. А вот 6 делится на 1, 2, 3, 6 и является составным.

Поэтому второй цикл необходим всего лишь для того чтобы пробежаться по всем делителям числа.

Но длительность этого цикла можно сократить двумя способами:

до j <= i / 2, т.к. после этого пойдут делители, которые никогда не могут поделить число нацело и в любом случае при делении будет что то дробное в промежутке от 1 до 2.
до квадратного корня: j <= Math.sqrt(i). Почему так можно?

Возьмем число 16. У него есть следующие делители:

16 : 1 = 16

16 : 2 = 8

16 : 4 = 4

16 : 8 = 2

16 : 16 = 1

После 4 все делители как будто бы отзеркаливаются. Это происходит после квадратного корня. Но так как квадратный корень это нечто дробное, то желательно округлить его и прибавить 1 или 2, чтобы точно быть уверенным что вы не пропустили, например делитель 7 в числе 49.

Полный код программы такой:

for (int n = 2; n <= 100; n++) {
    boolean isPrime = true;
    double squareRoot = Math.sqrt(n) + 2;
    int r = 2;
    while (r <= squareRoot && isPrime) {
        if (n % r == 0) isPrime = false;
        r++;
    }
    System.out.print(isPrime ? (n + " ") : "");
}

БЛОГ НА HUSL

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

Ответы (1 шт):