Tablica w porządku nieparzystym - rubin, algorytm, liczby pierwsze, faktorowanie wstępne, faktoryzacja

Napisałem to, aby znaleźć pierwszą faktoryzację liczby num. Daje prawidłowe odpowiedzi (na przykład 2, 3, 2, 3, 2 dla num 72), ale wychodzi w nieparzystej kolejności. Nie mogę zrozumieć, dlaczego. Zastanawiałem się, czy ktoś widzi coś, czego nie rozumiem.

$primes = [2]
$factors = []
num = 72
max = num

def isprime(n)
$primes.each do |x|
if n % x == 0 then
return
end
end
$primes.push(n)
return
end

i = 3
while i <= max
isprime(i)
i += 1
end

while !($primes.include?(num))
$primes.each do |x|
if num % x == 0 then
$factors.push(x)
num /= x
end
end
end
$factors.push(num)

puts $factors

Odpowiedzi:

Musisz przełamać $primes.each zapętlaj, jak tylko znajdziesz czynnik, lub będzie on za każdym razem wypełniał pętlę.

while !($primes.include?(num))
$primes.each do |x|
if num % x == 0 then
$factors.push(x)
num /= x
break
end
end
end
$factors.push(num)

P.S: Po prostu trzymałem się strony algorytmicznej i zignorowałem stronę Ruby.

Twoja wewnętrzna pętla działa w ten sposób. Rozważ, że testujesz numer 72.
Twoja tablica liczb pierwszych będzie [2,3,5,7...]

w $primes.each do |x| loop w pierwszej iteracji przetestuje num = 72 przeciwko 2 i dodaj go do factor szyk

Inner Iteration 1 => factors = [2], x = 2 , num = 36
Inner Iteration 2 => factors = [2,3], x = 3 , num = 12
Inner Iteration 3 => factors = [2,3], x = 5 , num = 12
Inner Iteration 3 => factors = [2,3], x = 7 , num = 12
Inner Iteration 3 => factors = [2,3], x = 11, num = 12

Teraz istnieje wewnętrzna iteracja i pierwsza pętla zaczyna się od nowa 2.

Inner Iteration 1 => factors = [2,3,2], x = 2 , num = 6
Inner Iteration 2 => factors = [2,3,2,3], x = 3 , num = 2

Pętla wewnętrzna zaczyna się od nowa

Inner Iteration 1 => factors = [2,3,2,3,2], x = 2 , num = 2

Musisz zrobić sobie przerwę w wewnętrznej pętli, aby zrobić pierwszą faktoryzację i wyjść.

while !($primes.include?(num))
$primes.each do |x|
if num % x == 0 then
$factors.push(x)
num /= x
break
end
end