Тема: Пошук дільників натуральних чисел

Пам'ятаєте ту програмістську забавлянку - http://adventofcode.com ?
Вона, а також рішення однієї задачі від пана koala, надихнуло мене на вивчення різних алгоритмів, хоча би простіших для початку. І ось цікава задача - номер 20 на тому сайті. Головна суть - пошук дільників. Я знайшов такий алгоритм - через факторизацію, тобто ми беремо підряд прості числа, і ділимо початкове число на ці прості числа. Тобто, в результаті можемо отримати щось таке:

24 = 2^3 * 3

. Всі дільники можна звідси легко отримати. Цей метод, здавалось би дійсно працює швидше, але... при розв'язанні даної задачі, швидшим виявився метод прямого пошуку дільників!

Ось моя реалізація 20 задачі на ruby:

Прихований текст
$primes_cache = []

def get_next_prime(index)
  if index <= $primes_cache.length
    #get from cache
    return $primes_cache[index-1]
  else
    #calculate new prime
    if not $primes_cache[-1]
      number = 2
    else
      number = $primes_cache[-1] + 1
    end
    while true
      is_prime = true
      $primes_cache.each do |prime|
        if number % prime == 0
          is_prime = false
          break
        end
      end # primes_cache.each
      if is_prime
        break
      else
        number += 1
      end
    end # while
    $primes_cache.push(number)
  end # else
  number
end

def get_prime_by_index(index)
  if index < 1
    return nil
  end

  prime = nil
  cache_length = $primes_cache.length
  if index <= cache_length
    #get from cache
    return $primes_cache[index-1]
  else
    while cache_length < index
      cache_length += 1
      prime = get_next_prime(cache_length)
    end
  end
  prime
end

def divisors_prime(number)
  div_array = [1]
  # number factorization
  #factor_array = []
  index = 1
  while number > 1
    prime = get_prime_by_index(index)
    mul_pos = 0
    while number % prime == 0
      number /= prime
      #factor_array.push(prime)
      # push real divisors
      temp_array = []
      mul_pos.upto(div_array.length-1) { |i| temp_array.push(div_array[i] * prime) }
      mul_pos += div_array.length
      div_array.concat(temp_array)
    end
    index += 1
  end
  div_array
end

def divisors(number)
  div_array = []
  x = 1
  while x <= Integer(Math.sqrt(number))
    if number % x == 0
      if x == Integer(number/x)
        div_array.push(x)
      else
        div_array.push(x, number/x)
      end
    end
    x += 1
  end
  div_array
end

def calculate_start(max_sum)
  sum = 0
  x = 1
  while sum < max_sum
    sum += x
    x += 1
  end
  x - 1
end

def main
  input = 29000000
  #input = 50000 # result - 3747
  #input = 70
  div_sum = input / 10
  start = 1
  #start = div_sum - 1
  #start = calculate_start(div_sum) * 2
  while true
    sum = divisors(start).inject { |sum, x| sum + x }
    if start % 10000 == 0
      print "Processing #{start} of #{div_sum-1}\n"
      puts "Sum #{sum}"
    end
    #if divisors(start).inject { |sum, x| sum + x } == div_sum
    if sum >= div_sum
      break
    elsif start >= div_sum - 1
      print "Can't find such number\n"
      break
    end
    start += 1
  end
  start
end

#load prime numbers from file
File.open('primes.txt') do |fin|
  fin.each_line { |line| $primes_cache.push(line.to_i) }
end

# UNCOMMENT NEXT LINE TO SOLVE PROBLEM
#print main

# UNCOMMENT NEXT LINE TO NOT RUN TESTS
#__END__

# test section

counter_p = 0
counter_s = 0
time_p = 0
time_s = 0
numbers = (100_000..1_000_000)
numbers.each do |number|
  start_time = Time.now
  divisors_prime(number)
  end_time = Time.now
  div_prime_time = end_time - start_time
  time_p += div_prime_time

  start_time = Time.now
  divisors(number)
  end_time = Time.now
  div_time = end_time - start_time
  time_s += div_time

  if div_prime_time > div_time
    puts "Number: #{number}, prime: #{div_prime_time}, simple: #{div_time}"
    counter_p += 1
  elsif div_prime_time < div_time
    counter_s += 1
  end
end
puts "Divisors prime losses:  #{counter_p}, time: #{time_p}"
puts "Divisors simple losses: #{counter_s}, time: #{time_s}"

Перед виконанням, Я за допомогою цих же функцій створив файл "primes.txt", куди завантажив 100 000 перших простих чисел. І час пошуку розв'язку через метод "divisors_prime" все одно більший, ніж через пошук дільників прямим методом divisors (звичайний цикл від 1 до кореня квадратного від числа).

Тести показують, що:

Divisors prime losses:  288032, time: 950.9318199240025
Divisors simple losses: 611969, time: 396.02343936400183

Тобто, пошук дільників через прості числа працюють швидше у 611969 раз із того проміжку (100 000 - 1 000 000), але загальний час виконання майже втричі перевищує час виконання на прямому методі, який "програв" майже втричі (288032 рази, коли він був дійсно швидший).

Ось, власне питання - що не так із моєю реалізацію? Який найкращий метод для розв'язання цієї задачі?

Подякували: Chemist-i, leofun012

2

Re: Пошук дільників натуральних чисел

Викладу і свій код на пітоні.

Прихований текст
def getdivisor(n):
    for i in range(2,n):
        if i*i>n:
            return n
        if n%i==0:
            return i
    return n
    
def div_repr(n):
    divisors=[]
    div=0
    while n>1:
        div=getdivisor(n)
        n//=div
        divisors.append(div)
    groups=[]
    div=0
    for i in divisors:
        if i!=div:
            groups.append([i,1])
            div=i
        else:
            groups[-1][1]+=1
    return ' * '.join(map(lambda xn:str(xn[0]) if xn[1]==1 else "%d**%d"%tuple(xn),groups))

if __name__=='__main__':
  import sys
  for line in sys.stdin:
    n=int(line); assert n>1
    print("%s == %d" % (div_repr(n), n))
    
Подякували: leofun011

3

Re: Пошук дільників натуральних чисел

Що ж, уже вкотре переконуюсь, що тут не дочекаюся відповіді на своє питання. Та й дійсно, адже секта свідків "Programmable Hyperlinked Pasta" не можуть вийти за рамки, на то це й секта.
Коротше кажучи, цікавість перемогла лінь і Я провів деякі дослідження та зумів таки пришвидшити алгоритм. Отож, проблема була в тому, що деякі числа уже могли бути простими, а тому їх варто одразу на це перевірити. Оскільки масив простих чисел впорядкований, то в цьому допоможе "бінарний пошук" (ось так його накидав тяп-ляп):

module Algorithms

  def Algorithms.search_bin(array, element, left=0, right = array.length)
    while true
      position = (left + right) / 2
      return position if array[position] == element
      return nil if right - left <= 1
      right = position if array[position] > element
      left = position if array[position] < element
    end
  end

end

Тоді, функція divisors_prime переписується ось так:

Прихований текст
def divisors_prime(number)
  div_array = [1]
  # number factorization
  index = 1
  right = $primes_cache.length
  while number > 1
    # check if number is already prime
    left = 0
    right = Algorithms.search_bin($primes_cache, number, left, right)
    if right
      temp_array = []
      0.upto(div_array.length-1) { |i| temp_array.push(div_array[i] * number) }
      div_array.concat(temp_array)
      return div_array
    else
      right = $primes_cache.length
    end
    # regular factorization
    prime = get_prime_by_index(index)
    mul_pos = 0
    while number % prime == 0
      number /= prime
      # push real divisors
      temp_array = []
      mul_pos.upto(div_array.length-1) { |i| temp_array.push(div_array[i] * prime) }
      mul_pos = div_array.length
      div_array.concat(temp_array)
    end
    index += 1
  end
  div_array
end

В результаті, відповідь отримується десь за 20-25 секунд, а тести тепер показують такі результати:

Divisors prime losses:  1971, time: 40.27258232800159
Divisors simple losses: 898030, time: 383.9376234210184

Ось, із 950 секунд стало 40 по тестах - одразу який величезний виграш! Всім дякую за увагу.

Подякували: leofun011

4

Re: Пошук дільників натуральних чисел

А ви перечитували ваше питання? Уявляли, як його сприйме людина поза контекстом?