CODEWITHSUNDEEP
rubyprimes
Nemo
Nemo

Reputation: 187

Finding smallest prime factor

I am trying to create a function that returns the smallest prime factor of a given number:

require 'prime'

def findSmallestPrimeFactor(number)
  return 2 if number.even?
  return number if Prime.prime? number
  arrayOfFactors = (1..number).collect { |n| n if number % n == 0 }.compact
  arrayOfFactors.each { |n| arrayOfFactors.pop(n) unless Prime.prime? n }
  return arrayOfFactors[0]
end

findSmallestPrimeFactor(13333) should return 67 but instead returns 1, which should not be happening since 1 should be removed from arrayOfFactors during line 7, as Prime.prime? 1 returns false

It sometimes returns nothing:

puts findSmallestPrimeFactor(13335) # => returns empty line

This issue only occurs when working with a number that is not even and is not prime, i.e lines 4 and 5 are ignored.

Also, when this is finished I will be passing some very large numbers through it. Is there any shorter or more efficient way to do lines 6-8 for larger numbers?

Upvotes: 1

Views: 758

Answers (2)

johnjps111
johnjps111

Reputation: 1170

If Prime.prime? is false for 1, it will fail the "if" and keeps going. Try making your array go from 3..sqrt(number)... which will exclude 1, and you've already established the number is odd, so leave out 2 too, and of course there's no need to look at anything higher than the square root either; (because factors always come in pairs a*b=n where a and b are factors; in the case of the square root, a = b... in all other cases, one is less than, and the other greater than, the square root).

Also, rather than gathering the entire collection, consider a regular loop that short circuits the instant it finds a prime factor: why find all factors if all you want is the smallest; (e.g. for 3333, you can quickly find out the smallest prime factor is 3, but would do a lot more steps to find all factors).

Upvotes: 1

Yu Hao
Yu Hao

Reputation: 122453

Since you are using the prime library, it has a prime_division method:

require 'prime'

13335.prime_division
# => [[3, 1], [5, 1], [7, 1], [127, 1]]
13335.prime_division[0][0]
# => 3

Upvotes: 3

Related Questions