Finding the largest prime factor without recursion

Ruby
1

I recently discovered a website called Project Euler and took a stab at
their questions. The first 2 were fine but then when I got to the 3rd
question, all hell broke loose and I started really questioning my
progress with Ruby.

The problem asks to find the largest prime factor of a number. I’ve
peeked at other peoples’ solutions online and noticed all of them used
recursion. However, I want to solve it without recursion. Without
further ado:

Assuming that num is an odd number, find the largest prime factor. So:
prime(99) => 11 prime(13195) => 29

Here is my code. The output keeps coming out as [3] if num = 99 and I
can’t figure out why.

def prime(num)
        arr = []
    p = []
    not_p = []
    # first I find all the numbers that num is divisible by
    for i in (2..num/2)
        if num % i == 0
             arr << i
        end
    end # this should output [3, 9, 11, 33]

    arr.each do |x| #  I loop through each element in the above

array
for i in (2…(x/2)) # I divide each element - x - by 2 b/c
it cannot be divisble by anything greater than its half
if x % i == 0 # if x is divisble by i
not_p << i # I push the i into array#not_p
end # keep looping until i reaches x/2
end
if not_p.length == 0 # if there are no values in
array#not_p, then I know x is a prime factor
p << x # so I push x into array#p
end
end
return p[-1] # returns the last element of the array, which is
the largest
end

2

Buson Li wrote in post #1166579:

I recently discovered a website called Project Euler and took a stab at
their questions. The first 2 were fine but then when I got to the 3rd
question, all hell broke loose and I started really questioning my
progress with Ruby.

The problem asks to find the largest prime factor of a number. I’ve
peeked at other peoples’ solutions online and noticed all of them used
recursion. However, I want to solve it without recursion. Without
further ado:

Assuming that num is an odd number, find the largest prime factor. So:
prime(99) => 11 prime(13195) => 29

Here is my code. The output keeps coming out as [3] if num = 99 and I
can’t figure out why.

def prime(num)
        arr = []
    p = []
    not_p = []
    # first I find all the numbers that num is divisible by
    for i in (2..num/2)
        if num % i == 0
             arr << i
        end
    end # this should output [3, 9, 11, 33]

    arr.each do |x| #  I loop through each element in the above

array
for i in (2…(x/2)) # I divide each element - x - by 2 b/c
it cannot be divisble by anything greater than its half
if x % i == 0 # if x is divisble by i
not_p << i # I push the i into array#not_p
end # keep looping until i reaches x/2
end
if not_p.length == 0 # if there are no values in
array#not_p, then I know x is a prime factor
p << x # so I push x into array#p
end
end
return p[-1] # returns the last element of the array, which is
the largest
en

not_p initialise should be in the ‘for i in (2…(x/2))’ loop

Here is a same algo, code more rubysh :

def bprime(num)
divs=(2…num/2).select {|i| num%i==0}
primes= divs.reject {|x| (2…(x/2)).any? {|i| x%i==0}}
return primes.last || num
end
p bprime 4
p bprime 5
p bprime 9
p bprime 12
p bprime 131711737
p bprime 99

D:\usr>ruby t.rb
2
5
3
3
37
11

3

Here is another way to get a list of prime numbers.

require ‘mathn’

p Prime.each(100).to_a

#> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61,
67, 71, 73, 79, 83, 89, 97]

Harry

Online Karnaugh map solver with circuit

4

Harry M. wrote in post #1169852:

Here is another way to get a list of prime numbers.

require ‘mathn’

p Prime.each(100).to_a

#> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61,
67, 71, 73, 79, 83, 89, 97]

mathn is deprecated, just require “prime” - which will add a
“prime_division” method to integers,enabeling:

13195.prime_division.last.first #=> 29