Problem:


Prime Factorization

Factorize a given integer n.

Input

n

An integer n is given in a line.

Output

Print the given integer n and :. Then, print prime factors in ascending order. If n is divisible by a prime factor several times, the prime factor should be printed according to the number of times. Print a space before each prime factor.

Constraints

2 ≤ n ≤ 109

Sample Input 1

12

Sample Output 1

12: 2 2 3

Sample Input 2

126

Sample Output 2

126: 2 3 3 7



Sample input:
12


Sample output:
12: 2 2 3

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import collections
import itertools


def prime_factorization(n):

    assert n > 0
    if n == 1:
        return collections.deque([1])
    else:
        result = collections.deque()
        for i in itertools.count(2):
            if i * i > n:
                break
            else:
                while n % i == 0:
                    n //= i
                    result.append(i)
        if n > 1:
            result.append(n)
        return result

if __name__ == "__main__":
    n = int(input())
    factors = prime_factorization(n)
    print("{n}: {factors}".format(n=n, factors=" ".join(map(str, factors))))

Submission status: Accepted

Solution code:
from math import sqrt

def is_prime(x):
    if x == 2:
        return True

    if x % 2 == 0 or x < 2:
        return False

    i = 3 
    x_sqrt = sqrt(x)
    while i <= x_sqrt:
        if x % i == 0:
            return False
        i += 2

    return True

def prime_numbers(x):
    i_a = list(range(2, x+1))
    p_a = list()
    e_a = sqrt(x)
    h = i_a[0]
    while h < e_a:
        h = i_a[0]
        p_a.append(h)
        for j in i_a:
            if j % h == 0:
                i_a.remove(j)
    p_a += i_a
    p_a.sort()

    return p_a

if __name__ == "__main__":
    i = int(input())
    n = i
    f = list()
    p_ns = prime_numbers(int(sqrt(n)))

    while not is_prime(n):
        for p in p_ns:
            if n % p == 0:
                f.append(p)
                n = int(n / p)
                break
    f.append(n)
    f.sort()

    print(str(i)+":", " ".join(map(str, f)))

Submission status: Accepted

Solution code:
import math

n = input()
prime = []
#find prime numbers in 1-sqrt(n)
m = int(math.sqrt(n))
for i in range(m+1):
    prime.append(True)
prime[0] = False
prime[1] = False

for i in range(2, int(math.sqrt(m))):
    if not prime[i]:
        continue
    else:
        for j in range(i+1, int(math.sqrt(m))):
            if j % i == 0:
                prime[j] = False

s = []
i = 2
num = n
while True:
    if i == int(math.sqrt(num))+1:
        s.append(str(n))
        break

    if not prime[i] or n % i != 0:
        i += 1
        continue

    if n % i == 0:
        s.append(str(i))
        n /= i
        if n == 1:
            break

st = " ".join(s)
print "%d: %s" % (num, st)

Submission status: Accepted

Solution code:
def prime_decomposition(n):
    prime_factors = []
    if n < 2:
        return prime_factors
    while n >= 2 and n % 2 == 0:
        prime_factors.append(2)
        n //= 2
    i = 3
    while i * i <= n:
        if n % i == 0:
            prime_factors.append(i)
            n //= i
        else:
            i += 2
    if n > 1:
        prime_factors.append(n)
    return prime_factors

n = int(input())
print(str(n)+':',*prime_decomposition(n))

Submission status: Accepted

Solution code:
import math
n = int(input())

def factorize_rec(n, factor):
    for i in range(2, math.floor(math.sqrt(n)) + 1):
        if n % i == 0:
            factor.append(i)
            return factorize_rec(n/i, factor)
    factor.append(int(n))
    return factor

def factorize(n):
    return factorize_rec(n, [])

print(str(n) +":", end=" ")
# for i in factorize(n):
#     print(i, end=" ")
print(*factorize(n), sep=' ')

Submission status: Accepted

Solution code:
def prime_fact(n):
    i = 2
    table = []
    while i*i<=n:
        while n%i ==0:
            n /=i
            table.append(i)
        i+=1
    if n>1:
        table.append(n)
    return table
n = input()
anslist = prime_fact(n)
print str(n)+":",
for ans in anslist:
    print str(ans),

Submission status: Accepted

Solution code:
def primefactor(x):
    fac=[]
    for i in xrange(2,int(x**0.5)+1):
        while x%i==0:
            fac+=[i]
            x=x/i
    if x!=1:
        fac+=[x]
    return fac

n=input()
ans=primefactor(n)
print(str(n)+":"+" "+" ".join(map(str,ans)))

Submission status: Accepted

Solution code:
import math
n = int(input())

def fac(m, p):
    step = 1 if p == 2 else 2
    for i in range(p, int(math.sqrt(m)+1), step):
        if m % i == 0:
            return i
    return m

result = str(n) + ":"
r = n
p = 2
while r != 1:
    p = fac(r,p)
    r = r//p
    result = result + " " + str(p)
print(result)

Submission status: Accepted

Solution code:
import math
n = int(input())

def factor(m, p):
    step = 1 if p == 2 else 2
    for i in range(p, int(math.sqrt(m)+1), step):
        if m % i == 0:
            return i
    return m

res = str(n) + ":"
p = 2
while n != 1:
    p = factor(n,p)
    n = n//p
    res = res + " " + str(p)
print(res)

Submission status: Accepted

Solution code:
n = input()
print "%d:"%n,
ans = []
x = 2
while x*x<=n:
    while n%x<1:
        ans += [str(x)]
        n /= x
    x += 1
if n-1: ans += [str(n)]
print " ".join(ans)

Submission status: Accepted

Solution code:
n = int(input())
print(str(n)+":",end = " ")

while n >= 4 and n % 2 == 0:
    print("2",end = " ")
    n //= 2
d = 3
q = n//d
while q >= d:
    if(n % d == 0):
        print(str(d),end = " ")
        n = q
    else:
        d += 2
    q = n // d
print(str(n))

Submission status: Accepted

Solution code:
def get_primes(n):
  lst = []
  for x in xrange(2, n+1):
    is_prime = True
    for i in xrange(len(lst)):
      if x % lst[i] == 0:
        is_prime = False
        break
      if x < lst[i]*lst[i]:
        break
    if is_prime:
      lst.append(x)
  return lst

n = int(raw_input())
lst = get_primes(10 ** 5)
answer = str(n) + ":"
for i in xrange(len(lst)):
  while True:
    if n % lst[i] == 0:
      answer += " " + str(lst[i])
      n /= lst[i]
    else:
      break
  if n == 1:
    break

if n != 1:
  answer += " " + str(n)

print answer

Submission status: Accepted

Solution code:
out = []
str_n = input()
n = int(str_n)
save = n
out.append(str_n+':')

i = 2
while i*i <= save:
  if n % i == 0:
    while n % i == 0:
      n //= i
      out.append(i)
  i += 1
if n > 1:
  out.append(n)

print(" ".join(map(str,out)))

Submission status: Accepted

Solution code:
def create_prime_list(limit):
    """ ??¨??????????????????????????§limit?????§????´???°?????????????±???????
    https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9
    """
    x = limit**0.5
    primes = []
    # print('x={0}'.format(x))
    nums = [x for x in range(2, limit+1)]
    while nums[0] <= x:
        primes.append(nums[0])
        current_prime = nums[0]
        nums = [x for x in nums if x % current_prime != 0]
    primes.extend(nums)
    # print(primes)
    return primes



def calc_divisors(n):
    """ n????????????????????¨?????§????????°????????? """
    if n in Primes:
        return [n]
    results = []
    i = 2
    start_num = n
    while n >= i**2:
        if n%i==0:
            while n%i==0:
                results.append(i)
                n //= i
            if n in Primes:
                results.append(n)
                n = 1
        i += 1
    #print('{0}????´???°: {1}'.format(start_num, results))
    if not results:
        results = [start_num]
    return results


Primes = set()
if __name__ == '__main__':
    # ??????????????\???
    target_number = int(input())
    # target_number = 999993031
    # target_number = 1463616



    # ?¨?????????????
    Primes = set(create_prime_list(int(10**4.5)+1))
    results = calc_divisors(target_number)

    # ???????????¨???
    print('{0}: {1}'.format(target_number, ' '.join(map(str, results))))

Submission status: Accepted

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

"""
input:
126

output:
126: 2 3 3 7
"""

import sys


def is_prime(n):
    if n == 2:
        return True
    elif n < 2 or not n % 2:
        return False

    return pow(2, n - 1, n) == 1


def prime_factorize(n):
    if is_prime(n):
        return [n]

    ans = []
    d = 2

    while pow(d, 2) <= n:
        while not n % d:
            ans.append(d)
            n //= d
        d += 1

    if n > 1:
        ans.append(n)

    return ans


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    n1 = int(_input[0])
    print(str(n1) + ':', *prime_factorize(n1))

Submission status: Accepted

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

"""
input:
126

output:
126: 2 3 3 7
"""

import sys


def is_prime(n):
    if n == 2:
        return True
    elif n < 2 or not n % 2:
        return False

    return pow(2, n - 1, n) == 1


def prime_factorize(n):
    if is_prime(n):
        return [n]

    ans = list()
    d = 2

    while pow(d, 2) <= n:
        while not n % d:
            ans.append(d)
            n //= d
        d += 1

    if n > 1:
        ans.append(n)

    return ans


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    n1 = int(_input[0])
    print(str(n1) + ':', *prime_factorize(n1))

Submission status: Accepted

Solution code:
import math

def factorize(n):
    p = n
    while True:
        if p % 2 == 0:
            p //= 2
            yield 2
        else:
            break

    r = 3
    while r < int(math.sqrt(p)+1):
        if p % r == 0:
            p //= r
            yield r
        else:
            r += 2

    if p != 1:
        yield p

n = int(input())
l = factorize(n)

print(str(n)+":",*list(l))

Submission status: Accepted

Solution code:
import math

def factorize(p):
    while p % 2 == 0:
        p //= 2
        yield 2

    r = 3
    while r < int(math.sqrt(p)+1):
        if p % r == 0:
            p //= r
            yield r
        else:
            r += 2

    if p != 1:
        yield p

n = int(input())
l = factorize(n)

print(str(n)+":",*list(l))

Submission status: Accepted

Solution code:
import math

def factorize(p):
    l = []
    while p % 2 == 0:
        p //= 2
        l.append(2)

    r = 3
    while r < int(math.sqrt(p)+1):
        if p % r == 0:
            p //= r
            l.append(r)
        else:
            r += 2

    if p != 1:
        l.append(p)

    return l

n = int(input())
l = factorize(n)

print(str(n)+":",*list(l))

Submission status: Accepted

Solution code:
import math

def factorize(p):
    l = []
    while p % 2 == 0:
        p //= 2
        l.append(2)

    r = 3
    while r < int(math.sqrt(p)+1):
        if p % r == 0:
            p //= r
            l.append(r)
        else:
            r += 2

    if p != 1:
        l.append(p)

    return l

n = int(input())
l = factorize(n)

print(str(n)+":",*l)

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-

n = int(input())
print(str(n)+':',end='')
array = []
count = 0
while True:
    if n == 999993031:
        break
    for i in range(2,n+1):
        if n%i == 0 and i != n:
            array.append(i)
            n = int(n/i)
            break
        if i == n:
            count += 1
            break
    if count == 24:
        break

array.append(n)
for i in range(len(array)):
    print(' ',array[i],sep = '',end='')
print('')

Submission status: Accepted

Solution code:
n=input()
print(n+': ',end='')
n=int(n);d=2
while n%d==0 and n>3:
    print(d,end=' ')
    n//=d
d+=1
m=n//d
while m>=d:
    if(n%d==0):
        print(d,end=' ')
        n=m
    else:d+=2
    m=n//d
print(n)

Submission status: Accepted

Solution code:
n = int(input())

def function(n):
    a = []
    if n < 2:
        return a
    while n%2 ==0:
        a.append(2)
        n = n//2
    i = 3
    while i*i <= n:
        if n%i ==0:
            a.append(i)
            n = n//i
        else:
            i += 2
    if n > 1:
        a.append(n)
    return a
print(str(n)+":",*function(n))

Submission status: Accepted

Solution code:
n = int(input())
orig_n = n
res=[]
i = 2
half_n = n // 2
root_n = int(n ** (1/2))
is_prime = True
while i <= (root_n):
    if orig_n % i == 0:
        is_prime = False
        break
    i += 1
if is_prime: res.append(orig_n)

while i <= half_n and not(is_prime):
    if n ==1:
        break
    if n % i == 0:
        n = n // i
        res.append(i)
        i = 1
    i += 1

print("{0}: {1}".format(orig_n, " ".join(map(str, res))))

Submission status: Accepted

Solution code:
import math
n = int(input())

def fac(m, p):
    step = 1 if p ==2 else 2
    for i in range(p, int(math.sqrt(m)+1), step):
        if m % i == 0:
            return i
    return m

result = str(n) + ':'
r = n
p = 2
while r > 1:
    p = fac(r,p)
    r = r//p
    result = result + " " + str(p)

print(result)

Submission status: Accepted

Solution code:
n = int(input())
ans = []

m = n

for p in range(2, n + 1):
    if p**2 > n or m == 1:
        break

    while m % p == 0:
        m //= p
        ans.append(p)

if m > 1:
    ans.append(m)

print('{}: '.format(n), end='')
print(*ans)

Submission status: Accepted

Solution code:
n = int(input())
print("{}:".format(n), end='')
x = int(pow(n, 0.5))+1
for i in range(2, x):
    while n % i == 0:
        print(" {}".format(i), end='')
        n //= i
print(' {}'.format(n) if n != 1 else '')

Submission status: Accepted

Solution code:
import sys
from math import sqrt

def solve():
    n = int(input())

    print('{}: '.format(n), end='')
    print(*prime_factorization(n))

def prime_factorization(n):
    if n < 2:
        return [n]

    res = []
    lim = int(sqrt(n))

    for p in range(2, lim + 1):
        while n % p == 0:
            res.append(p)
            n //= p

    if n > 1:
        res.append(n)

    return res

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import math
N = int(input())
n = N
a = []
for i in (n for _ in ([2], range(3, int(math.sqrt(n))+1, 2)) for n in _ ):
    while n%i==0:
        a.append(str(i))
        n //= i
if n>1:
    a.append(str(n))
print(str(N)+": "+(" ".join(a)))

Submission status: Accepted

Solution code:
n=int(input())
s=str(n)+":"
b=True
d=n
i=2
while b:
 if d%i==0:
  d/=i
  s+=' '+str(i)
  i-=1
 b=i<d**0.5
 i+=1
if d!=1:s+=' '+str(int(d))
print(s)

Submission status: Accepted

Solution code:
def is_prime(x):
    if x == 1:
        return False
    elif x == 2:
        return True
    elif x % 2 == 0:
        return False
    l = x ** 0.5
    n = 3
    while n <= l:
        if x % n == 0:
            return False
        n += 2
    return True
 
def solve():
    n = int(input())
    print("{}: ".format(n), end='')
    ans = []
     
    while n % 2 == 0:
        n //= 2
        ans.append(2)
 
    d = 3
    while n >= d:
        if is_prime(d):
            while n % d == 0:
                n //= d
                ans.append(d)
        if is_prime(n):
            ans.append(n)
            break
        d += 2
 
    print(*ans)
 
solve()

Submission status: Accepted

Solution code:
def is_prime(x):
    # Perform prime number discrimination for odd numbers of 3 or more.
    return pow(2, x - 1, x) == 1

def solve():
    n = int(input())
    print("{}: ".format(n), end='')
    if is_prime(n):
        print(n)
    else:
        ans = []
        while n % 2 == 0:
            n //= 2
            ans.append(2)
        d = 3
        while d <= n ** 0.5:
            if is_prime(d):
                while n % d == 0:
                    n //= d
                    ans.append(d)
            d += 2
        if is_prime(n):
            ans.append(n)
        print(*ans)

solve()

Submission status: Accepted

Solution code:
# Aizu Problem NTL_1_A: Prime Factorize
#
import itertools
import sys, math, os

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input2.txt", "rt")


def factors(n):
    f = 2
    increments = itertools.chain([1,2,2], itertools.cycle([4,2,4,2,4,6,2,6]))
    for incr in increments:
        if f*f > n:
            break
        while n % f == 0:
            yield f
            n //= f
        f += incr
    if n > 1:
        yield n

N = int(input())
print("%d: %s" % (N, ' '.join([str(_) for _ in list(factors(N))])))

Submission status: Accepted

Solution code:
n=int(input())

def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n //= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(n)
  return table
print("{0:d}".format(n)+": "+" ".join(map(str,prime_decomposition(n))))

Submission status: Accepted

Solution code:
# coding=utf-8
import array
import math


def sieve_of_eratosthenes(end):
    """
    :type end: int
    :rtype: array.array
    """
    # noinspection PyUnusedLocal
    is_prime = array.array('B', (True for i in range(end+1)))
    is_prime[0] = False
    is_prime[1] = False

    primes = array.array("L")
    for i in range(2, end+1):
        if is_prime[i]:
            primes.append(i)
            for j in range(i * 2, end+1, i):
                is_prime[j] = False
    return primes


if __name__ == '__main__':
    N = int(input())
    n = N
    upper_n = int(math.sqrt(n)) + 1
    # print(upper_n)
    prime_list = sieve_of_eratosthenes(upper_n)
    # print(prime_list)
    elementary_number_list = array.array("L")
    counter = 0

    while counter < len(prime_list):
        if n % prime_list[counter] == 0:
            elementary_number_list.append(prime_list[counter])
            n //= prime_list[counter]
        else:
            counter += 1

    if n != 1:
        elementary_number_list.append(n)

    print("{0}: {1}".format(N, ' '.join(map(str, elementary_number_list))))

Submission status: Accepted

Solution code:
m=input();n=int(m);s=n**.5;a=[];i=6
while n%2==0:a+=[2];n//=2
while n%3==0:a+=[3];n//=3
while i<s:
 if n%(i-1)==0:a+=[i-1];n//=i-1
 elif n%(i+1)==0:a+=[i+1];n//=i+1
 else:i+=6
if n>1:a+=[n]
elif n==int(m):a+=[m]
print(m+':',*a)

Submission status: Accepted

Solution code:
p=lambda x:print(x,end=' ')
n=input()
p(n+':')
n=int(n);s=n**.5
while n%2==0 and n>3:
    p(2)
    n//=2
d=3
while s>d and n>d:
    if n%d==0:
        p(d)
        n//=d
    else:d+=2
print(n)

Submission status: Accepted

Solution code:
p=lambda x:print(x,end=' ')
n=input();p(n+':')
n=int(n);s=n**.5
while n%2==0 and n>3:p(2);n//=2
d=3
while s>d and n>d:
 if n%d==0:p(d);n//=d
 else:d+=2
print(n)

Submission status: Accepted

Solution code:
p=lambda x:print(x,end=' ')
n=input();p(n+':')
n=int(n);s=n**.5;d=3
while n%2==0 and n>3:p(2);n//=2
while s>d and n>d:
 if n%d>0:d+=2
 else:p(d);n//=d
print(n)

Submission status: Accepted

Solution code:
p=lambda x:print(x,end=' ')
n=input();p(n+':')
n=int(n);s=n**.5
while n%2==0 and n>3:p(2);n//=2
d=3
while s>d and n>d:
 if n%d>0:d+=2
 else:p(d);n//=d
print(n)

Submission status: Accepted

Solution code:
p=lambda x:print(x,end=' ')
n=input()
p(n+':')
n=int(n)
s=n**.5
while n%2==0 and n>3:p(2);n//=2
d=3
while s>d and n>d:
 if n%d>0:d+=2
 else:p(d);n//=d
print(n)

Submission status: Accepted

Solution code:
p=lambda x:print(x,end=' ')
n=input();p(n+':')
m=n=int(n)
while n%2==0 and n>3:p(2);n//=2
d=3
while d*d<m and n>d:
 if n%d>0:d+=2
 else:p(d);n//=d
print(n)

Submission status: Accepted

Solution code:
# coding: UTF-8
#@document_it
def document_it(func):
    def new_function(*args,**kwargs):
        print('Running function:', func.__name__)
        print('Positional arguments:', args)
        print('Kewword arguments:', kwargs)
        result = func(*args,**kwargs)
        print('Result:', result)
        return result
    return new_function

def divide(n):
    import math
    m = math.ceil(math.sqrt(n))
    d = 2
    while d <= m:
        if n % d == 0:
            return d,n//d
        d += 1
    return n,1

def exe():
    string = input()
    n = int(string)
    factors=[]
    d,a = divide(n)
    factors.append(str(d))
    while a != 1:
        d,a = divide(a)
        factors.append(str(d))
    ans = string + ': ' + ' '.join(factors)
    print(ans)
 
if __name__ == '__main__':
    exe()

Submission status: Accepted

Solution code:
N = int(input())
M = N
result = []
i = 2
while i * i <= N:
    while N % i == 0:
        N //= i
        result.append(i)
    i += 1
if N > 1:
    result.append(N)
print(str(M) + ": " + " ".join(map(str, result)))

Submission status: Accepted

Solution code:
import math
n = int(input())
nc = n
result = []
i = 2
while i <= math.sqrt(n):
    if n%i == 0:
        n //= i
        result.append(str(i))
    else:
        i += 1
if n != 1:
    result.append(str(n))
print(str(nc) + ": " + " ".join(result))

Submission status: Accepted

Solution code:
import math
n=input()
N=n
a=[]

x=2
while x*x<=N:
	while n%x==0:
		a.append(str(x))
		n=n/x
	if n==1: break
	x+=1
else:
	a.append(str(n))


print str(N)+": "+" ".join(a)

Submission status: Accepted

Solution code:
import math

def simple_prime_factrize(x):
    pfs = []
    s = math.sqrt(x)
    for y in range(2, math.ceil(s)):
        if x == 1: break
        while True:
            if x%y == 0:
                pfs.append(y)
                x = x/y
            else:
                break
    if len(pfs) == 0:
        pfs.append(x)
    elif x > s:
        pfs.append(int(x))
    return pfs
    
n = int(input())
print(str(n) + ': ' + ' '.join([str(x) for x in simple_prime_factrize(n)]))

Submission status: Accepted

Solution code:
import math

s = "{0}:"
s2 = " {0}"
def prime_factorize(n):
	m = math.sqrt(n)+1
	i = 2
	prime = []
	while n != 1 and i < m:
		if n % i == 0:
			prime.append(i)
			n //= i
		else:
			i += 1
	if n != 1:
		prime.append(n)
	return prime
n = int(input())
lst = prime_factorize(n)
print(s.format(n),end="")
for i in range(len(lst)):
	print(s2.format(lst[i]),end="")
print()

Submission status: Accepted

Solution code:
n = int(input())
from math import sqrt,ceil

def is_prime(n):
    if n == 1: return False
    if n == 2: return True
    for i in range(2, ceil(sqrt(n))+1):
        if n % i == 0: return False
    return True

def prime_factorization(n):
    if is_prime(n):return [n]
    factor = []
    for i in range(2, ceil(sqrt(n))+1):
        if not is_prime(i): continue
        q,r = divmod(n, i)
        if r == 0:
            n = q
            factor.append(i)
            q,r = divmod(n, i)    
            while r == 0:
                n = q
                factor.append(i)
                q,r = divmod(n, i)
    if n != 1:
        factor.append(n)
    return factor

factor = sorted(prime_factorization(n))
print("%d:"%n, *factor)

Submission status: Accepted

Solution code:
n = int(input())
a = []
now = n
for i in range(2, n):
    while now % i == 0:
        now //= i
        a.append(i)
    if i * i > n:
        break
if now != 1:
    a.append(now)
print(str(n) + ":", end = "")
for i in a:
    print(" " + str(i), end = "")
print()

Submission status: Accepted

Solution code:
import math

def make_divisors(n):
    divisors = []
    for k in range(2, math.floor(math.sqrt(n))+1):
        if n % k == 0:
            divisors.append(k)
            divisors.append(n // k)

    divisors.append(n)

    return sorted(divisors)

def main():
    n = int(input())
    original_n = n

    factors = []
    divisors = make_divisors(n)

    i = 0
    while True:
        if n == 1:
            break

        if n % divisors[i] == 0:
            n //= divisors[i]
            factors.append(divisors[i])
        else:
            i += 1

    print("{}: {}".format(
        original_n,
        " ".join(list(map(str, factors)))
    ))

main()

Submission status: Accepted

Solution code:
import math

n = m = int(raw_input())
r = int(math.sqrt(n))
sqrt = int(math.sqrt(r))
p = [1]*r
p[0] = 0
for i in range(1,sqrt):
    if p[i]:
        p[2*i+1::i+1] = [0 for x in range(2*i+1,r,i+1)]
 
prime=[]
for i in range(r):
    if p[i]:
        prime.append(i+1)

a = []
for i in range(len(prime)):
    if n % prime[i] == 0:
        j = prime[i]
        while n % j == 0:
            n /= j
            a.append(j)
if n == m:
    print str(m)+":",m
elif n != 1:
    print str(m)+":"," ".join(map(str, a)),n
else:
        print str(m)+":"," ".join(map(str, a))

Submission status: Accepted

Solution code:
n = int(input())

def factorization(n):
    arr = []
    temp = n
    for i in range(2,int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i,cnt])
    if temp != 1:
        arr.append([temp,1])

    if arr == []:
        arr.append([n,1])

    return arr

f = factorization(n)
l = []
for i in range(len(f)):
    for _ in range(f[i][1]):
        l.append(str(f[i][0]))

ans = ' '.join(l)
print(f'{str(n)}: ' + ans)

Submission status: Accepted

Solution code:
def ifprime(n):
    if n%2==0:
        print(' 2',end="")
        return(int(n/2))
    else:
        for i in range(3,int(n**0.5)+1):
            if n%i==0:
                print(f' {i}',end="")
                return(int(n/i))
        print(f' {n}',end="")
        return(1)
n=int(input())
print(f'{n}:',end="")
while 1:
    n=ifprime(n)
    if n==1:break
print()

Submission status: Accepted

Solution code:
import math
n=int(input())
print(str(n)+":",end=" ")

ans=[]
i=2
while i<=math.sqrt(n):
    if n%i==0:
        ans.append(i)
        n=n//i
    else:
        i+=1
ans.append(n)
print(*ans)

Submission status: Accepted

Solution code:
def factorization(n):
    L=[]
    temp=n
    print(n,end='')
    print(':',end='')
    for i in range(2,int(n**(1/2)//1)+1):
        if temp%i==0:
            c=0
            while temp%i==0:
                c+=1
                temp//=i
            L.append([i,c])
            for j in range(c):
                print('',i,end='')
    
    if temp!=1:
        print('',temp,end='')
        
    print( )
    
n=int(input())
factorization(n)

Submission status: Accepted

Solution code:
N = int(input())

res = []
x = N
y = 2
while y*y <= x:
    while x % y == 0:
        res.append(y)
        x//= y
    y += 1
if x > 1:
    res.append(x)
print("%d:"%N,*res)

Submission status: Accepted

Solution code:
n=int(input())
ans=[str(n)+":"]
i=2
while i*i<=n:
    while n%i==0:
        n//=i
        ans.append(i)
    i+=1
if n!=1:ans.append(n)
print(*ans)

Submission status: Accepted

Solution code:
def factorization(n):
    L=[]
    temp=n
    print(n,end="")
    print(":",end="")
    for i in range(2,int(n**(1/2))+1):
        if temp%i==0:
            c=0
            while temp%i==0:
                c+=1
                temp//=i
            L.append([i,c])
            for j in range(c):
                print("",i,end="")
    if temp!=1:
        print("",temp,end="")
    if L==[]:
        pass
    print()
    return L
n=int(input())
factorization(n)

Submission status: Accepted

Solution code:
n = int(input())

ans = []
x = n
y = 2
while y*y <= x:
    while x % y == 0:
        ans.append(y)
        x //= y
    y += 1
if x > 1:
    ans.append(x)
print("%d:" % n, *ans)

Submission status: Accepted

Solution code:
b = int(input());
n = b;
a = []
while n % 2 == 0:
    a.append(2)
    n //= 2
f = 3
while f * f <= n:
    if n % f == 0:
        a.append(f)
        n //= f
    else:
        f += 2
if n != 1:
    a.append(n)

print("{}:".format(b),end = '');
for i in range(0,len(a)):
    print('',a[i],end = '');
print();

Submission status: Accepted

Solution code:
n = int(input())
a = []
x = n
y = 2
while y*y <= x:
    while x%y == 0:
        a.append(y)
        x //= y
    y += 1
if x > 1:
    a.append(x)
print('%d:'%n,*a)

Submission status: Accepted

Solution code:
n=int(input())
print(n,': ',sep='',end='')
a=2
A=[]
while a*a<=n:
    while n%a==0:
        n //= a
        A.append(str(a))
    a+=1
if n>1:
    A.append(str(n))
A=' '.join(A)
print(A)

Submission status: Accepted

Solution code:
n=int(input())
print(str(n)+': ',end='')
a = []
i = 2
while i*i<=n:
    while n%i==0:
        n//= i
        a.append(i)
    i+=1
if n!=1:
    a.append(n)

print(*a)

Submission status: Accepted

Solution code:
def f(n):
    a=[]
    while n%2==0:
        a.append(2)
        n=n//2
    f=3
    while f*f<=n:
        if n%f==0:
            a.append(f)
            n=n//f
        else:
            f+=2
    if n!=1:
        a.append(n)
    return(a)
    
n=int(input())
a=f(n)
b=[str(i) for i in a]
A=" ".join(b)
print(f"{n}: {A}")

Submission status: Accepted

Solution code:
import math
n=int(input())
nn=n
a=[]
i=2
while i<=math.sqrt(n):
    if n%i==0:
        n//=i
        a.append(str(i))
    else:
        i+=1
if n!=1:
    a.append(str(n))
print(str(nn)+": "+" ".join(a))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

n = int(input())
print(n, ": ", sep = "", end = "")

pri = []
while n % 2 == 0:
   pri.append(2)
   n //= 2

for i in range(3, int(n ** 0.5 + 1)):
   while n % i == 0:
      pri.append(i)
      n //= i
   i += 2

if n != 1:
   pri.append(n)

for i in range(len(pri)):
   print(pri[i], end = "")
   if i < len(pri) - 1:
      print(" ", end = "")
print("")

Submission status: Accepted

Solution code:
n=int(input())
A=[]
B=n
while n%2==0:
    n//=2
    A.append(2)
while n%3==0:
    n//=3
    A.append(3)
while n%5==0:
    n//=5
    A.append(5)
while n%7==0:
    n//=7
    A.append(7)
if n>=10000000:
    A.append(n)
else:
    for j in range(3,n+1,2):
         while n%j==0:
            n//=j
            A.append(j)
print(B,end="")
print(':',*A)

Submission status: Accepted

Solution code:
N = int(input())
N_ = N
arr = []

for x in range(2,int(pow(N,0.5) + 1)):
    while N % x == 0:
        arr.append(x)
        N = N // x

if N != 1:
    arr.append(N)

print(f"{N_}:", *arr)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def calc_prime_factors(n, count=False):
    """Trial division"""
    factors = []
    # factor: 2
    while n % 2 == 0:
        factors.append(2)
        n //= 2
    # factor: 3, 5, 7, 11, ...
    f = 3
    root_n = int(n ** 0.5) + 1
    while f <= root_n:
        if n % f == 0:
            factors.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        factors.append(n)
    return factors


def main():
    N = int(input())

    factors = calc_prime_factors(N)

    print("{}:".format(N), " ".join(map(str, factors)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
n = int(input())
m = n
l = []
for i in range(2, int(math.sqrt(n))+1):
    while m % i ==0:
        l.append(i)
        m = m // i
        if m == 1:
            break

if m != 1:
    l.append(m)
print("{}: ".format(n),end="")
print(*l)

Submission status: Accepted

Solution code:
def fact(n):
    from subprocess import Popen, PIPE
    return [*map(int, Popen(["factor", str(n)], stdout=PIPE).communicate()[0].split()[1:])]
n = int(input())
print(f"{n}:", *fact(n))

Submission status: Accepted

Solution code:
n = int(input())
x =[]

y = 2
z = n

while y*y <= z:
    while z % y == 0:
        x.append(y)
        z = z//y
    y += 1
    
if z > 1:
    x.append(z)

print("%d:" % n,*x)

Submission status: Accepted

Solution code:
n = int(input())
N = n
print(N,":",sep="",end=" ")

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    b = 3
    while b * b <= n:
        if n % b == 0:
            a.append(b)
            n //= b
        else:
            b += 2
    if n != 1:
        a.append(n)
    return a
    
A = prime_factorize(n)
print(*A)

Submission status: Accepted

Solution code:
n = int(input())
factors = []
p = 2
m = n
while p * p <= m:
    if m % p == 0:
        m //= p
        factors.append(p)
        #m //= p
    else:
        p += 1
if m != 1:
    factors.append(m)
print(f'{n}:', *factors)