Программа для поиска простых чисел.Глава 2 Самопроверка Шильдт Java-руководство для начинающих - PullRequest
Новая
       13

Программа для поиска простых чисел.Глава 2 Самопроверка Шильдт Java-руководство для начинающих

0 голосов
/ 19 марта 2019

В разделе «Самотестирование» главы 2 «Руководства по Java для начинающих» Шильдта есть упражнение по написанию программы, которая находит все простые числа от 2 до 100.

Правильный ответ, который дает автор: 

class Prime {
    puЬlic static void main(String args[]) {
        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 a prime number."); 
        }
    }
}

Я не могу понять две вещи

1) Состояние второго цикла FOR: 

j <= i/j;

Это какой-то математический алгоритм для поиска простых чисел?

Моя версия условия выглядит как 

j < i;

2) Если в условии второго цикла поставить i <= j вместо i < j, то вывод программы будет пустым. Почему?

Спасибо за помощь!

Объяснение второго вопроса:

Когда я решил эту проблему, опираясь на «мою» версию определения простого числа, мой код выглядел так: 

for(i=2; i < 100; i++) {
            isprime = true;
            for (j=2; j <= i; j++)
                if((i%j) == 0) isprime = false;
            if (isprime)
                System.out.println(i +" - is a prime number."); 
        }

Обратите внимание на состояние второго цикла: я <= j. Меньше или равно </p>

Если вы полагаетесь на «мое» определение простого числа, то знак равенства в условии должен быть.

Попробуйте запустить программу. Вывод будет пустым.

Но если условие удаляет знак равенства for (j=2; j < i; j++), программа будет работать правильно.

в чем причина?

1 Ответ

1 голос
/ 19 марта 2019

Давайте сосредоточимся на этих for петлях. 

        for(i=2; i < 100; i++) {
            isprime = true;
            for (j=2; j <= i/j; j++)
                if((i%j) == О) isprime = false;
            if (isprime)
                System.out.println(i +" - is a prime number."); 
        }

Первый цикл повторяет все числа, которые вы хотите проверить. Достаточно легко понять, он просто говорит: «Я хочу выполнить следующий тест для всех чисел от 2 до 100». 

for (j=2; j <= i/j; j++)
    if((i%j) == О) isprime = false;

Теперь этот цикл - чистая математика. Математически, простое число:

- натуральное число больше 1, которое не может быть образовано умножение двух меньших натуральных чисел.

(источник: Википедия)

Поэтому вы перебираете все числа, которые при умножении образуют i.

Но вам действительно нужно? Если, например, i = 3 * 25, нужно ли вам итерировать до 25, чтобы узнать, что я не простое число?

Ответ, очевидно, нет, так как после проверки на j = 3 вы уже знаете, что я составной.

Математически существует несколько алгоритмов для проверки, является ли число простым или составным. Но разумно правильный способ сделать это - проверить, является ли число кратным любого числа от 2 до его собственного квадратного корня . Вы выполняете округленную версию этого.

Проверка всех чисел от 2 до i избыточна по причинам, указанным выше.

РЕДАКТИРОВАТЬ: Ответ на 2)

При использовании 

for (j=2; j <= i; j++)
    if((i%j) == 0) isprime = false;

вы говорите компилятору прекратить цикл после выполнения теста на j==i. Конечно, когда j равно i, (i% j) == 0 всегда принимает значение true.

В неинформативных терминах вы проверяете, состоит ли число из любого числа, кроме 1, включая саму себя , тогда как вам следует проверять, состоит ли оно из любого числа, кроме 1 и сам .

Это связано с тем, что в Java реализованы циклы for: они останавливаются, когда среднее условие оценивается как ложное.

...