Как эта программа для поиска простых чисел работает?

Question

Мне пришлось написать простую программу для печати простых чисел от 2 до 100.

Сначала я сделал некоторое исследование о том, что такое простое число. Я пробовал в течение долгого времени, и, наконец, я посмотрел ответ в книге, так как я не успевал каждый раз писать 100% рабочий код.

Я понимаю код ответа по большей части, но одну часть я не понимаю. Позвольте мне попытаться объяснить. Во-первых здесь код из книги:

// Find prime numbers between 2 and 100. 
class Prime { 

    public static void main(String args[]) { 
     int i, j; 
     boolean isprime; 
     for(i=2; i < 100; i++) { 
      isprime = true; 
      // see if the number is evenly divisible 
      for(j=2; j < i/j; j++) 
       // if it is, then it's not prime 
       if((i%j) == 0) isprime = false; 
      if(isprime) 
       System.out.println(i + " is prime."); 
     } 
    } 
} 

Хорошо, так что я знаю, что это: простое число можно разделить только на себя и на 1.

Позвольте мне взять номер 4 первых, это не простое, так как оно также может быть разделено на 2. Таким образом, в коде я следую за циклами for, но я застрял в части «видеть, является ли число равномерно делимым». В случае 4, то 4%4 не имеет остатка, поэтому он является ложным из-за части ==0.

Таким образом, isprime является ложным. Тем не менее, я читаю его неправильно или неправильно думаю, потому что, если взять первое число, например 5, я получаю то же самое: 5%5 не имеет остатка, потому что 5/5 == 1. Таким образом, в этом случае 5%5 также равен 0, поэтому isprime также должен быть ложным, но в этом случае число 5 является простым числом.

Так что я действительно не понимаю, как эта проверка работает в коде.

В начале i 2 и j не 2, так что вы получите 2%2, и никакого остатка, но 2 тоже простое число, так что я знаю, что я вижу это неправильно где-то.

Если кто-то может объяснить, как это работает в точности, я искал час в Интернете, но не смог его найти.

Answer 1

У вас небольшая ошибка в заголовке внутреннего контура.

// ... 
for(j=2; j <= i/j; j++) 
// ... 

Таким образом, вместо < вы должны использовать <=.

Answer 2

Лучший способ попытаться понять это, он помещает System.out.println внутри цикла со значениями i, j.

Я делаю это для вас, 2, 3,4 и 5. (только 4 не является простым).

с i = 2 -> Условие петли равно 2 < 2/2 ложно, вы не заходите внутрь цикла, это просто.

с i = 3 -> Условие петли равно 2 < 3/2 ложно, вы не заходите в петлю, это просто.

с i = 4 -> Условие петли равно 2 < 4/2 ложно, вы не заходите внутрь цикла и его простое.может быть, условие цикла должно быть < =

с г = 5 -> состояние петли 2 < 5/2 верно, вы идете внутри цикла, и если условие ложно, то добавить 1 к J и выполните цикл: 5/3 ложно, вы не заходите в цикл, это просто.

Answer 3

Ваша проблема в секунду для цикла

for(j=2; j < i/j; j++) 

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

условие должно быть:

for(j=2; j <= i/j; j++) 

это даст вам правильный результат.

Answer 4

Во-первых, следует сказать - и уже упоминалось в других ответах - что код, который вы получили из книги, неверен (или, возможно, вы пропустили его копирование). Состояние внутреннего контура должно быть

for(j=2; j <= i/j; j++) 

один важный урок из этого является то, что вы должны попробовать запустить даже примеры книги, чтобы увидеть, если они работают. Если вы запустили это, вы бы увидели, что он составляет 4,9,25,49 в качестве основного, когда это не так.

Но ваше чтение кода было неверным. Вы сказали, что 4 считается не простым, потому что 4%4 == 0. Но на самом деле простое число разрешено делиться само по себе (любое число). Так что, действительно, тестирование простого числа путем деления его само по себе не сработает.

Давайте посмотрим, что это такое. Вы понимаете внешний цикл - это дает вам кандидаты, чтобы проверить, являются ли они главными или нет.

Затем он работает следующим образом: предположим, что текущий кандидат является простым. Попытайтесь разделить его на все возможные делители. Если какой-либо из делителей делит его равномерно, отметьте его как «не простое».

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

Таким образом, петля i представляет кандидатов, а петля j представляет собой потенциальные делители. Возьмите номер 15 в качестве примера i.

• Начало j с 2. i/j является 15/2 который 7. 2 < 7, поэтому мы идем внутри цикла.
  • Есть 2 делитель 15? Нет, это не так. Ничего не сделано.
• j сейчас 3. i/j - 15/3, который является 5. 3 < 5, поэтому мы продолжим.
  • Является ли 3 делителем 15? Да! Поэтому установите isprime=false.
• j сейчас 4. i/j - 15/4, который является 3. 4 < 3 есть описание товара false, поэтому прекращаем.

Как вы можете видеть, шаг с j=3 выше набор isprime в false, поэтому мы не печатаем его - это не простое.

Теперь давайте возьмем реальное простое число, как 13:

• Начало j с 2. i/j является 13/2 который 6. 2 < 6, поэтому мы идем внутри цикла.
  • Есть 2 делитель из 13? Нет, это не так. Ничего не сделано.
• j сейчас 3. i/j - 13/3, который является 4. 3 < 4, поэтому мы продолжим.
  • Есть 3 делитель из 13? Нет, это не так. Ничего не сделано.
• j сейчас 4. i/j - 13/4, который является 3. 4 < 3 есть описание товара false, поэтому прекращаем.

Ни один из следующих этапов: isprime - false. Он по-прежнему true, поэтому число 13 является простым и мы его печатаем.

Теперь у нас есть трюк, какие кандидаты мы предлагаем для j. Наивно, человек, пишущий это в первый раз, подумает, что кандидаты должны иметь все числа от 1 до i, за исключением 1 и i. Поэтому они напишут петлю, как:

for (j = 2; j < i; j++) 

Но это расточительно. Зачем? Предположим, вы проверили номер 15. Вы обнаружили, что 3 является делителем для него. Как так? Потому что 15 = 3 x 5. Но это означает, что 5 также является делителем. Вам не нужно проверять делитель, который, если вы разделите его, вы получите делитель, который вы уже тестировали. Поэтому нет необходимости тестировать 5, потому что мы уже протестировали 3.

Итак, опять же, наивные программисты могли бы решить, что мы можем просто проверить половину кандидатов:

for (j = 2; j <= i/2; j++) 

Но на самом деле, с математической точки зрения, это еще расточительно. Действительно, мы должны идти только до квадратного корня i. Зачем? Потому что если делитель j больше квадратного корня i, такой, что j x k = i, то k будет меньше квадратного корня i. Если k было больше, то j x k было бы больше, чем sqrt(i) x sqrt(i), что означает, что они j x k > i. Но мы знаем, что они равны i!

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

Итак, это то, что тестирует ваш цикл-кандидат. Это в основном простой способ написания

for (j = 2; j <= Math.sqrt(i); j++) 

Без вызова Math класс и без преобразования целых чисел в парном разряде.

Но, как я сказал с самого начала, важно, чтобы условие было <=, а не <. Для чисел, которые являются квадратами простых чисел (4 = 2 x 2, 9 = 3 x 3), единственным правильным делителем является число, равное , равное их квадратному корню.

---

последнее замечание: эта книга пример еще расточительно, так как он не остановить проверку после того, как он нашел один делитель, который делает число не простое. Найти один делитель достаточно. Один из способов сделать это, чтобы изменить условие цикла, как это:

for (j = 2; isprime && j <= i/j; j++) 

Так цикл будет продолжаться только до тех пор, как мы по-прежнему есть основания полагать, что число является простым. После j, который отмечает isprime как false, цикл автоматически остановится.

(И, конечно же, этот алгоритм не самый лучший алгоритм. Есть лучшие алгоритмы. Это только тот, с которого все начинаются).

---

Ответы на вопросы, заданные в комментариях:

Внутренний цикл всегда выполняется заново. Подумайте об этом так:

Если петля говорит:

for (int i = 0; i < 3; i++) { 
    doSomething(); 
} 

Это эквивалентно

doSomething(); 
doSomething(); 
doSomething(); 

Так что, если "что-то делать" часть сама по себе петля:

for (int i = 0; i < 3; i++) { 
    for (int j = 0; j < 2; j++) { 
     runSomething(); 
    } 
} 

эквивалентен:

for (int j = 0; j < 2; j++) { 
    runSomething(); 
} 
for (int j = 0; j < 2; j++) { 
    runSomething(); 
} 
for (int j = 0; j < 2; j++) { 
    runSomething(); 
} 

Так вы видите, каждый раз это новый j, который начинается с нуля.

Что касается вопроса о фигурных скобках: официально, то формат for утверждения:

for (initialization; termination; increment) 
    statement 

Оператор может быть один оператор, как вызов метода, внутренний цикл, в если заявление или что-то еще. В этом случае он не нуждается в фигурных скобках. Или оператор может быть блоком , который представляет собой пару фигурных скобок, которая содержит ноль или более операторов.Вы привыкли видеть блок, и в самом деле рекомендуется всегда использовать блок, а не один оператор, так как легче добавлять утверждения.

Answer 5

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

класс primeNum {

public static void main(String args[]){ 

    int x = 2; 
    int y = 2; 
    int count; 
    System.out.println("The prime numbers between 2 and 100 are: "); 

    while (x < 100) { 
     count = 0; 
     y = 2; 

     while (y <= x) { 

      if (x % y == 0) { 
       count ++; 
      } 
     ++y; 
     } 
       if (count == 1) { 
        System.out.println(" " + x); 
      } 

     ++x; 
    } 
} 

}