Дано ціле число, що не менше 2. Виведіть його найменший натуральний дільник, відмінний від 1. Формат вхідних даних

Вводиться ціле позитивне число.

Формат вихідних даних

Виведіть відповідь до задачі.

Sample Input:

15
Sample Output:

3

ответ 31

код на Ruby 22

for i in 1..40
    s = i.to_s(2)
    k = 0
    s.chars().each {|c| k += 1 if c == "1" }
    s += (k % 2).to_s + "0"
    p [i, s, s.to_i(2)]
end

вывод
[1, "110", 6]
[2, "1010", 10]
[3, "1100", 12]
[4, "10010", 18]
[5, "10100", 20]
[6, "11000", 24]
[7, "11110", 30]
[8, "100010", 34]
[9, "100100", 36]
[10, "101000", 40]
[11, "101110", 46]
[12, "110000", 48]
[13, "110110", 54]
[14, "111010", 58]
[15, "111100", 60]
[16, "1000010", 66]
[17, "1000100", 68]
[18, "1001000", 72]
[19, "1001110", 78]
[20, "1010000", 80]
[21, "1010110", 86]
[22, "1011010", 90]
[23, "1011100", 92]
[24, "1100000", 96]
[25, "1100110", 102]
[26, "1101010", 106]
[27, "1101100", 108]
[28, "1110010", 114]
[29, "1110100", 116]
[30, "1111000", 120]
[31, "1111110", 126]
[32, "10000010", 130]
[33, "10000100", 132]
[34, "10001000", 136]
[35, "10001110", 142]
[36, "10010000", 144]
[37, "10010110", 150]
[38, "10011010", 154]
[39, "10011100", 156]
[40, "10100000", 160]

Следующее число, большее 125₁₀, равно 126₁₀ или 1111110₂
Посмотрим, может ли оно получиться по заданному алгоритму.
На шаге 2а определяется "бит четности" путем подсчета количества единиц в двоичной записи числа. Если оно четно, к записи числа справа дописывается 0, если нечетно - единица.
На шаге 2б повторяются действия предыдущего шага.
Отбросим две правые цифры в записи 1111110₂ и посмотрим, как на получившемся числе работает предложенный алгоритм.
1111110 ⇒ 11111, число единиц нечетное, дописываем 1, получаем 111111, теперь число единиц четное, дописываем 0 и получаем 1111110, т.е. как раз то число, которое у нас было при переводе 126 в двоичную систему счисления.
А исходное число - это 11111₂ = 31₁₀
ответ: 31