Генерация простых чисел в Ruby (Codewars kata: простые числа)

Question

Я решил ката Codewars, но не могу отправить его, потому что мой код занимает слишком много времени.У многих людей была эта проблема, но мы не видим решения.Проблема в том, что генерация простых чисел занимает слишком много времени (более 12 с) (я генерирую простые числа методом).

На моем компьютере мне может потребоваться класс Prime, и это решает проблему.Но в Codewar нельзя требовать класса Prime, поэтому мой метод генерации простых чисел слишком медленный.

Любая помощь?

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

Answer 1

Более продвинутый вариант может выглядеть следующим образом:

# 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.
#

Это работает на устаревшей машине с медленным процессором CORE 2 Duo.

Answer 2

Ну, для начала вам действительно нужно протестировать Math.sqrt (n) .to_i + 1, который должен помочь для больших n значений.

Это потому, что если существует фактор, где n = a * b, то либо

Если a == b == sqrt (n) # В основном, определение sqrt

или

Если a! = b;a sqrt (n)

Если a и b меньше, чем sqrt (n), то a * b n

Во-вторых, и это более сложно, вам нужно только проверить простые числа до этого предела.Я мог бы представить схему, где простые числа кэшируются.

Надеюсь, это поможет.