Понимание этой программы Ruby для поиска простых чисел

avatar
Red is Purple
8 апреля 2018 в 00:59
129
1
0

Я новичок в Ruby и читал об этой программе, которая находит простые числа.

Этот пример попал в учебник, после разговора о циклах (пока и до) он показал этот пример.

Я нахожу это довольно запутанным. Какова цель Prime_flag? Почему J установлено как 2?

(j <= i / 2) -- Этого я не понимаю.

j = j + 1 -- какова цель этого.

Прошу прощения за длинный вопрос, но любая помощь приветствуется. Пожалуйста и спасибо вам. 

# Initialize our counter
i = 1

# i: [0, 100]
while (i <= 100)
  # Initialize prime flag 
  prime_flag = true
  j = 2
  # Test divisibility of i from [0, i/2]
  while (j <= i / 2)
    # puts " i ==> " to i.to_s + " j ==> " + j.to_s 
    if (i % j == 0)
      prime_flag = false
      # break
    end 
    j = j + 1
  end
  # We found a prime!
  if prime_flag
    puts "Prime ==> " + i.to_s"
  end 
  # Increment the counter
  i += 1
end
Источник

Ответы (1)

avatar
vcsjones
8 апреля 2018 в 01:11
1

Цикл while считает от 2 до половины i и проверяет, является ли оно простым.

Почему J установлено равным 2?

Простое число — это число, у которого нет делителей, кроме единицы и самого себя. Если j начинается с 1, конечно, 1 является множителем числа. Если бы мы включили 1, то код считал бы, что ни одно из чисел не является простым, потому что он считал бы 1 множителем.

(j <= i / 2)

Цикл while проверяет до половины числа. Технически, вам нужно проверить только квадратный корень из числа.

j = j + 1 -- для чего это нужно.

Нам нужно увеличить j, чтобы перейти к следующему числу. По сути, программа делает что-то вроде:

  1. Начать с j на 2.
  2. Разделяется ли i на j?
    1. Да? Очистить основной флаг.
  3. Установить j следующим числом, 3.
  4. Разделяется ли i на j?
    1. Да? Очистить основной флаг.
  5. Повторить до половины i

В приведенном вами примере break закомментировано, и я не знаю, почему. break было бы неплохо сделать. По сути, это говорит: «Хорошо, мы нашли множитель для i, нам не нужно продолжать поиск дополнительных множителей.

.

Какова цель Prime_flag?

prime_flag используется для отслеживания, были ли найдены какие-либо факторы для i. Переменная начинается как истина, поэтому «Да», предположим, что число простое. Как только мы находим множитель, он устанавливает для него значение false, указывая на то, что i не является простым.

Red is Purple
8 апреля 2018 в 04:42
0

j <= i/2 (Если нам нужно найти только его квадратный корень, зачем написана эта строка кода?

vcsjones
8 апреля 2018 в 11:35
0

@RedisPurple, вероятно, автор учебника этого не знал. Проверка до половины i не делает код «неправильным», просто неэффективным.