Liczby pierwsze

Zielona szkoła
1

Aby sprawdzić czy dana liczba jest liczbą pierwszą, można to zrobić na wiele sposobów. Ale ja na początek wybrałem wersję najprostszą, czyli metodę dzielenia. Można napisać taki kod:

num = gets.chomp.to_i
prime = 1

for i in (2..(num - 1))
  if num % i == 0
    prime = 0
    break
  end
end

if prime == 1
  puts "Liczba #{num} jest pierwsza."
elsif prime == 0
  puts "Liczba #{num} nie jest pierwsza."
end

ale czy jest on poprawny? Chodzi mi o zastosowanie pętli for. Czy lepiej (a może ładniej) jest stosować takie konstrukcje?

2.upto(num - 1) do |i|
  if num % i == 0
    prime = 0
    break
  end
end

albo

num_range = 2..(num - 1)
num_range.each do |i|
  if num % i == 0
    prime = 0
    break
  end
end

Czy to nie ma znaczenia? Oczywiście wszystkie wersje liczą to samo, ale chodzi mi o wybór konwencji przy pisaniu kodu.

2

Po pierwsze powinieneś zacząć od pierwiastka z num a nie num - 1 :wink:
Ja wybrałbym ostatnią wersję - ale jestem początkującym niech wypowiedzą się starzy wyjadacze:)

3

Specjalnie zacząłem od (num - 1), aby obliczenia były trochę dłuższe, bo ich szybkość porównuję z analogicznym kodem napisanym w Pythonie.

4

Możesz również skorzystać z gotowej biblioteki:

http://ruby-doc.org/stdlib-1.9.3/libdoc/prime/rdoc/Prime.html

5

Tak, to wiem, ale specjalnie nie chciałem skorzystać z niej. Chodziło mi o kod liczący na “piechotę”.

6

Taka mała ciekawostka: przy sprawdzaniu podziału wystarczy sprawdzać zakres 1…Math.sqrt(n).floor.

7

Chciałem przeliczyć cały zakres, aby wydłużyć czas obliczeń.

8

Jeśli koniecznie chcesz sprawdzać każdą po kolei od 2 do n - 1 to chyba najprościej używając potęgi Enumerable:

def prime?(n)
  return false if n < 2
  (2...n).none? { |x| (n % x).zero? }
end

prime? 2 #=> true
prime? 10 #=> false
9

No tak, czytałem że daną rzecz można zrobić w Ruby na 100 sposobów, i jak widać była to prawda :wink: . Ciekawy kod, dzięki.