I am beginning with Ruby and trying to solve the third problem on the
Euler project. When I run the below code I get the following results:
5
7
13
29
65
145
377
1015
2639
But 65, 145, 377, 1015 and 2639 should not be part of the results since
they are not prime.
For some reason I only seem to be testing these numbers:
5, 7, 13, 29, 35, 91, 203, 455 and 1885 (and that must be why 65, 145,
377, 1015, and 2639 are included in the results). But I can’t figure
out why and been looking at this for too many hours now and I am
stumped.
My code:
composite_number_array = []
composite_array_test = []
first_number = 13195
sr_number = Math.sqrt(first_number).ceil
(2…sr_number).each do
|i|
if (first_number % i == 0)
sr_number_pair = first_number / i
composite_number_array.push(i)
composite_number_array.push(sr_number_pair)
end
end
composite_number_array.uniq!
composite_number_array.sort!
puts composite_number_array
puts “beginning work”
composite_number_array.each do
|z|
composite_array_test.push(z)
last_num = z
(2…last_num).each do
|a|
if last_num % a == 0
composite_number_array.delete(last_num)
end
end
end
puts “the results are”
puts composite_number_array
puts “the test array was”
puts composite_array_test
Does anyone see anything wrong? Can anyone point me in the right
direction?
Thank you!
I would avoid modifying an array as you’re running through it as you do
with ‘composite_number_array’. It’s better to make a copy of it and when
running .each on composite_number_array, remove the filtered elements
from your copy. If you notice, your arrays are alternating because when
elements of your original array are filtered out, .each goes to the next
POSITION - meaning a element gets skipped by each. So try:
composite_copy = composite_number_array.dup
puts “beginning work”
composite_number_array.each do |z|
composite_array_test.push(z)
last_num = z
(2…last_num).each do |a|
if last_num % a == 0
composite_copy.delete(last_num)
end
end
end
If you print ‘composite_copy’ it will give you [5, 7, 13, 29] now.
Beyond this, I noticed some other issues with your approach. I don’t see
the point of ‘sr_number_pair’ which gets the other factor resulting in
first_number and adds it to composite_number_array. Since all prime
factors will never be greater than the square root of that number, it’s
completely unnecessary to do this (since you check for factors up to the
square root anyway).
The other issue is that when filtering your array of factors, you test
up to the number itself (- 1) to check for primality when it’s not
necessary to go that far. There’s no reason to check beyond its square
root. This is not a problem for something like 13,195, but for big
numbers (like the billions that project euler uses), it will take a
very, very long time if you check every number. You also need a way to
stop the process if it finds a filtering match early on… eg - checking
78,995 should stop at ‘5’, not go all the way to
78,994. I think you may know this based on your factor check but just
maybe didn’t apply it to your end filtering.
I don’t want to give a solution, but your approach is also off. There
are better ways to find the prime factors than getting all the factors
up to the square root and then filtering the ones that aren’t prime. Do
a search for ‘finding prime factors’ to find better methods.
Good luck with your learning!
Just a few other comments… I think it helps to make your code more
readable. Adding comments in your code to make it clear what you’re
trying to do helps, and might get members (far smarter and knowledgeable
than me) to post replies.
It’s also good to work on making your code more modular. It helps with
readability and with fixing problems. For example, the part where you
start checking if elements in your array are prime could be written as
its own function. eg…
def is_prime?®
add steps to check if r is prime & return true or false
end
composite_number_array.each do |z|
if z.is_prime?
composite_copy.delete(z)
end
end
Now suddenly we know what you’re trying to do even without comments. It
becomes more readable and easier to fix. You could then reuse this
function any time you need to check for primes instead of rewriting it
every time. I know ruby has it’s own thing for primes but it’s good
practice to write your own. You could even add this to a separate file
and just include it when you need (after you’ve made sure it works
well).