#!/usr/bin/env python
# coding: utf-8

# #Факторизация целых чисел

# ##Алгоритм пробных делений
# 
# Простой алгоритм, перебирающий все возможные делители $d$, начиная с $2$, пока $d^2\le a$. Четные пробные делители (кроме $2$) пропускаются.

# In[1]:


def factor(a):
    '''
    Разложение числа на простые множители.

    Функция находит все простые делители заданного числа.

    Вход:
        a - заданное число, a ≥ 2
    
    Выход:
        список всех простых делителей числа n;
             каждый делитель повторяется столько раз,
             какова его кратность; делители расположены 
             в порядке возрастания
    '''

    divisors = []
    while a % 2 == 0:
        divisors.append(2)
        a //= 2
    d = 3
    while d*d <= a:
        while (a % d) == 0:
            divisors.append(d)
            a //= d
        d += 2
    if a > 1:
        divisors.append(a)
    return divisors


# ###Пример

# In[2]:


for a in xrange(1, 101):
    print a, factor(a)


# In[3]:


get_ipython().run_line_magic('time', 'factor(11111111111111111)')


# In[4]:


get_ipython().run_line_magic('time', 'factor(1111111111111111111)')


# ##Усовершенствованный алгоритм пробных делений
# 
# В качестве пробных делителей рассматриваются числа $2$, $3$ и числа вида $d = 6k \pm 1$, где $k\in{\bf N}$

# In[5]:


def factor(a):
    '''
    Разложение числа на простые множители.

    Функция находит все простые делители заданного числа.

    Вход:
        a - заданное число, a ≥ 2
    
    Выход:
        список всех простых делителей числа n;
             каждый делитель повторяется столько раз,
             какова его кратность; делители расположены 
             в порядке возрастания
    '''

    divisors = []
    while a % 2 == 0:
        divisors.append(2)
        a //= 2
    while a % 3 == 0:
        divisors.append(3)
        a //= 3
    k = 1
    while True:
        d = 6*k - 1          # пробный делитель
        if d*d > a:
            break
        while a % d == 0:
            divisors.append(d)
            a //= d
        d = 6*k + 1          # пробный делитель
        if d*d > a:
            break
        while a % d == 0:
            divisors.append(d)
            a //= d
        k += 1
    if a > 1:
        divisors.append(a)
    return divisors


# ### Пример

# In[6]:


for a in range(2, 21):
    print a, factor(a)


# In[7]:


get_ipython().run_line_magic('time', 'factor(11111111111111111)')


# In[8]:


get_ipython().run_line_magic('time', 'factor(1111111111111111111)')