CODEWITHSUNDEEP
ruby
AlbertMunichMar
AlbertMunichMar

Reputation: 1866

Generate prime numbers in Ruby (Codewars kata: Primes in numbers)

I have solved a Codewars kata, but I can not submit it because my code takes too long. A lot of people had this problem, but we can not see the solution. The problem is, that generating the prime numbers takes too long (more than 12s) (I generate the primes with a method).

In my computer, I can require the class Prime, and this solves the problem. But in Codewar one can not require the class Prime, therefore, my method of generating prime numbers is too slow.

Any help?

require "pry"

def primeFactors(n)
  start_time = Time.now
  puts start_time
  # find prime numbers smaller than n

  nums = (2..(n-1)).to_a
  odd_nums = nums.select { |num| num.odd? }

  primes = odd_nums.select do |num|
    is_prime(num)
  end

  end_time = Time.now
  duration = end_time - start_time
  puts end_time

  # divide until mod is 1
  dividend = n
  res_primes = []

  while dividend > 1

    primes.each do |prime| # prime divisor
      new_dividend = dividend.to_f / prime
      remainder = dividend % prime
      if remainder.zero?
        dividend = new_dividend
        res_primes << prime
        break
      end
    end
  end

  freqs = {}
  res_primes.each do |res_prime|
    freqs[res_prime] = res_primes.count(res_prime)
  end

  res_string = []
  freqs.keys.each do |key|
    if freqs[key] == 1
      res_string << "(#{key})"
    else
      res_string << "(#{key}**#{freqs[key]})"
    end
  end

  res_string.join
end


def is_prime(n)
  (2..n/2).none?{|i| n % i == 0}
end

Upvotes: 1

Views: 327

Answers (2)

Peter Camilleri
Peter Camilleri

Reputation: 1912

The more advanced option might look like this:

# Is this number a prime?

module PrimeChecker

  @prime_cache = [2,3]

  def self.prime?(n)
    search_limit = Math.sqrt(n).to_i + 1
    last_cache = @prime_cache[-1]

    while last_cache < search_limit do
      last_cache += 2
      @prime_cache << last_cache if PrimeChecker.prime?(last_cache)
    end

    @prime_cache.each do |pn|
      return true if pn > search_limit
      return false if (n % pn) == 0
    end

    true
  end

end

# Sample run
#
# 31 mysh>%=PrimeChecker.prime?(1_000_000_000_000)
# false
# Elapsed execution time = 1.592 seconds.
#

This running on an elderly machine with a slow CORE 2 Duo processor.

Upvotes: 2

Peter Camilleri
Peter Camilleri

Reputation: 1912

Well for starters you really only need to test to Math.sqrt(n).to_i + 1 that should help for larger n values.

This is because if a factor exists where n = a * b then either

If a == b == sqrt(n) # Basically the defn of sqrt

or

If a != b; a < sqrt(n); b > sqrt(n)

If both a and b are less than sqrt(n) then a * b < n and If both a and b are greater than sqrt(n) the a * b > n

Secondly, and this is more complex, you only need to test prime numbers to that limit. I could envision a scheme where primes are cached.

Hope this helps.

Upvotes: 2

Related Questions