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 ≤ 10 9   Sample Input 1 12 Sample Output 1 12: 2 2 3 Sample Input 2 126 Sample Output 2 126: 2 3 3 7

Solution (Python):
N = int(input())
n = N
m = N ** 0.5
L = []
i = 3

print(str(N) + ': ', end = '')

while n%2 == 0:
    n = n/2
    L.append(2)

while i <= m:
    while n%i == 0:
        n = n/i
        L.append(i)
    i += 2

if n not in L:
    L.append(int(n))  

if 1 in L:
    L.remove(1)

if len(L) == 0:
    L.append(N)

print(' '.join(map(str, L)))

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def primeFact(n):
    """
    nの素因数をlistで返す
    """
    factors = []
    i = 2
    while i*i <= n:
        if n % i == 0:
            n //= i
            factors.append(i)
        else:
            i += 1
    if n > 1:
        factors.append(n)
    return factors


n = int(input())
print(str(n)+": "+" ".join(map(str, primeFact(n))))

Solution (Python):
def prime_factorize(n):
    x=2
    lim=int(n**0.5)
    factors=[]
    while n!=1 and x<=lim:
        if n%x==0:
            n//=x
            factors.append(x)
        else:
            x+=1
    if n!=1:
        factors.append(n)
    return factors

n=int(input())
print(n,': ',sep='',end='')
print(*prime_factorize(n))

Solution (Python):
import math
import random
class Prime:
    seed_primes=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
    def is_prime(self,n):
        is_prime_common=self.is_prime_common(n)
        if is_prime_common is not None:return is_prime_common
        if n<2000000:return self.is_prime_brute_force(n)
        return self.is_prime_miller_rabin(n)
    def is_prime_common(self,n):
        if n==1:return False
        if n in Prime.seed_primes:return True
        if any(map(lambda x:n%x==0,self.seed_primes)):return False
    def is_prime_brute_force(self,n):
        for k in range(2,int(math.sqrt(n))+1):
            if n%k==0:return False
        return True
    def is_prime_miller_rabin(self,n):
        d=n-1
        while d&1==0:d>>=1
        witnesses=self.get_witnesses(n)
        for w in witnesses:
            y=pow(w,d,n)
            while d!=n-1and y!=1and y!=n-1:
                y=y*y%n
                d<<=1
            if y!=n-1and d&1==0:return False
        return True
    def get_witnesses(self,num):
        def _get_range(num):
            if num<2047:return 1
            if num<1373653:return 2
            if num<25326001:return 3
            if num<3215031751:return 4
            if num<2152302898747:return 5
            if num<3474749660383:return 6
            if num<341550071728321:return 7
            if num<3825123056546413051:return 9
            return 12
        return self.seed_primes[:_get_range(num)]
    def gcd(self,a,b):
        if a<b:return self.gcd(b,a)
        if b==0:return a
        while b:a,b=b,a%b
        return a
    @staticmethod
    def f(x,n,seed):
        p=Prime.seed_primes[seed%len(Prime.seed_primes)]
        return(p*x+seed)%n
    def find_factor(self,n,seed=1):
        if self.is_prime(n):return n
        x,y,d=2,2,1
        count=0
        while d==1:
            count+=1
            x=self.f(x,n,seed)
            y=self.f(self.f(y,n,seed),n,seed)
            d=self.gcd(abs(x-y),n)
        if d==n:
            return self.find_factor(n,seed+1)
        return self.find_factor(d)
    
    def find_factors(self,n):
        primes={}
        if self.is_prime(n):
            primes[n]=1
            return primes
        while n>1:
            factor=self.find_factor(n)
            primes.setdefault(factor,0)
            primes[factor]+=1
            n//=factor
        return primes
n=int(input())
d=Prime().find_factors(n)
a=[]
for i in d:
    a.extend([i]*d[i])
print('%d:'%n,*sorted(a))

Solution (Python):
def prime(num):
    if num==1:
        return False
    elif num==2 or num==3:
        return True
    else:
        for i in range(2,int(num**0.5)+1):
            if num%i==0:
                return False
        else:
            return True

n=int(input())
tmp=n
plist=[]
if prime(n):
    print('{}: {}'.format(n,n))
else:
    while 1:
        for i in range(2,tmp+1):
            if tmp%i==0:
                plist.append(i)
                tmp=tmp//i
                break
        else:
            break
    print('{}: {}'.format(n,' '.join(map(str,plist))))

Solution (Python):
from collections import defaultdict

def factorize(n):
    result = defaultdict(int)
    m = n
    p = 2
    while p*p <= m:
        while n % p == 0:
            n = n // p
            result[p] += 1
        p += 1
    if n > 1:
        result[n] += 1
    return result

n = int(input())
factors = factorize(n)
ans = '{}:'.format(n)
for p, num in factors.items():
    ans += ' {}'.format(p) * num
print(ans)

Solution (Python):
from collections import defaultdict

def prime_factorization(n):
    result = defaultdict(int)
    if n < 2:
        return result
    while n >= 2 and n % 2 == 0:
        result[2] += 1
        n //= 2
    p = 3
    while p*p <= n:
        while n % p == 0:
            n = n // p
            result[p] += 1
        p += 2
    if n > 1:
        result[n] += 1
    return result

n = int(input())
factors = prime_factorization(n)
ans = '{}:'.format(n)
for p, num in sorted(factors.items()):
    ans += ' {}'.format(p) * num
print(ans)

Solution (Python):
from collections import defaultdict

def prime_factorization(n):
    result = defaultdict(int)
    if n < 2:
        return result
    while n % 2 == 0:
        result[2] += 1
        n //= 2
    p = 3
    while p*p <= n:
        while n % p == 0:
            n = n // p
            result[p] += 1
        p += 2
    if n > 1:
        result[n] += 1
    return result

n = int(input())
factors = prime_factorization(n)
ans = '{}:'.format(n)
for p, num in sorted(factors.items()):
    ans += ' {}'.format(p) * num
print(ans)

Solution (Python):
a=int(input())
n=a
i=2
fc=[]
while i*i<=a:
  while a%i==0:
    a//=i
    fc.append(i)
  i+=1
if a>1:
  fc.append(a)
print(str(n)+": "+" ".join(str(b) for b in fc))

Solution (Python):
def primeFactorize(n):
    factors = []

    while n % 2 == 0:
        factors.append(2)
        n //= 2

    i = 3
    max_factor = n ** 0.5

    while i <= max_factor:
        while n % i == 0:
            factors.append(i)
            n //= i
            max_factor = n ** 0.5
        i += 2

    if n > 1:
        factors.append(n)

    return factors


n = int(input())
factors = primeFactorize(n)
print("{0}:".format(n), end="")
for factor in factors:
    print(" {0}".format(factor), end="")
print()

Solution (Python):
import sys
from heapq import heappush, heappop

def sieve(n):
    is_prime = [True] * (n + 1)
    prime_list = []
    
    is_prime[0] = is_prime[1] = False
    prime_list.append(2)
    
    for i in range(3, n + 1, 2):
        if is_prime[i]: prime_list.append(i)
        for j in range(i * i, n + 1, i):
            is_prime[j] = False
            
    return prime_list
    
primes = sieve(40000)

def factorization(n):
    ret = []
    for prime in primes:
        while n % prime == 0:
            ret.append(prime)
            n /= prime
    if n > 1: ret.append(n)
    
    return ret
            
    
    
if __name__ == '__main__':
    n = sys.stdin.readline()
    n = int(n)
    
    ans = factorization(n)
    sys.stdout.write(str(n) + ': ')
    sys.stdout.write(' '.join(map(lambda x: str(x), ans)) + '\n')

Solution (Python):
def prime_decomposition(n):
    '''by cocodrips'''
    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 = int(raw_input())
print str(n) + ': '+ ' '.join(map(str,prime_decomposition(n)))

Solution (Python):
import math
def sieve(n):
    p = [1] * (n + 1)
    p[0] = p[1] = 0
    
    for i in range(math.ceil((n + 1) ** 0.5)):
        if p[i]:
            for j in range(2 * i, len(p), i):
                p[j] = 0
    return p

def prime_factor(n):
    p = sieve(int(n ** 0.5))
    factor = []
    for pi in compress(count(0), p):
        while n % pi == 0:
            n //= pi
            factor.append(pi)

    if n != 1:
        factor.append(n)
    return factor

from sys import stdin
from itertools import compress, count

readline = stdin.readline


n = int(readline())
print('{}: '.format(n) + ' '.join(map(str, prime_factor(n))))

Solution (Python):
from copy import deepcopy
from functools import reduce

class Divisor:
    def __init__(self, n):
        """ make divisors list and prime factorization list of n"""
        number = n
        if number == 1:
            self.primeFactorization = {1: 1}
        else:
            self.primeFactorization = {}
            for i in range(2, int(n**0.5)+1):
                cnt = 0
                while number % i == 0:
                    cnt += 1;
                    number //= i
                if cnt > 0:
                    self.primeFactorization[i] = cnt
            if number > 1:
                self.primeFactorization[number] = 1

    def primeFactors(self):
        return deepcopy(self.primeFactorization)

    def numDivisors(self):
        """ the number of divisors """
        if self.primeFactorization.get(1, 0) == 1:
            return 1
        numDiv = 1
        for _, cnt in self.primeFactorization.items():
            numDiv *= cnt+1
        return numDiv

    def sumDivisors(self):
        return reduce(lambda x, y: x * y, [sum(p**i for i in range(n+1)) for p, n in self.primeFactorization.items()])

def divisorsList(n):
    divsList = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divsList.append(i)
            if n // i != i:
                divsList.append(n//i)
    return sorted(divsList)

N = int(input())
p = Divisor(N)
print('{}: '.format(N), end='')
ans = []
print(*[d for d, cnt in sorted(p.primeFactors().items()) for i in range(cnt)])

Solution (Python):
def p(n):
    l = [1]*(n+1)
    l[0] = l[1] = 0
    for i in range(2,int(n ** 0.5) + 1):
        if l[i]:
            for j in range(2*i, n+1, i):
                l[j] = 0
    return l
n = input()
l = []
l += [str(n)+":"]
from itertools import compress, count
P = p(int(n ** 0.5))
for i in compress(count(0), P):
    while n % i == 0:
        n /= i
        l += [i]
if n != 1: l += [n]
print " ".join(map(str,l))

Solution (Python):
def p(n):
    l = [1]*(n+1)
    l[0] = l[1] = 0
    for i in range(2,int(n ** 0.5) + 1):
        if l[i]:
            for j in range(2*i, n+1, i):
                l[j] = 0
    return l
n = input()
l = []
l += [str(n)+":"]
from itertools import compress
P = p(int(n ** 0.5))
for i in compress(xrange(0,n), P):
    while n % i == 0:
        n /= i
        l += [i]
if n != 1: l += [n]
print " ".join(map(str,l))

Solution (Python):
n = input()
l = []
l += [str(n)+":"]
i = 2
while i * i <= n:
    while n % i == 0:
        l += [i]
        n /= i
    i += 1
if n > 1: l += [n]
print " ".join(map(str,l))

Solution (Python):
from math import sqrt, floor
from collections import deque


def prime_generator():
    prime = set()
    yield 2
    i = 3
    while True:
        for d in prime:
            if not (i % d):
                break
        else:
            yield i
            prime.add(i)
        i += 2


nstr = input()
n = int(nstr)
limit = floor(sqrt(n))
a = deque()

for p in prime_generator():
    if p > limit:
        if n > 1:
            a.append(n)
        break
    while not (n % p):
        a.append(p)
        n = n // p
        limit = floor(sqrt(n))

a.appendleft(nstr + ':')
print(*a)

Solution (Python):
from math import sqrt, floor
from collections import deque


def divide_repeat(p):
    global n, a, limit
    while not (n % p):
        a.append(p)
        n = n // p
        limit = floor(sqrt(n))


nstr = input()
n, p = int(nstr), 3
limit = floor(sqrt(n))
a, i = deque(), 3

divide_repeat(2)

while p <= limit:
    divide_repeat(p)
    p += 2

if n > 1:
    a.append(n)

print(nstr + ': ', end='')
print(*a)

Solution (Python):
from math import sqrt
from collections import deque


def divide_repeat(p):
    global n, a, limit
    while not (n % p):
        a.append(p)
        n = n // p
        limit = sqrt(n)


nstr = input()
n, p = int(nstr), 3
limit = sqrt(n)
a, i = deque(), 3

divide_repeat(2)

while p <= limit:
    divide_repeat(p)
    p += 2

if n > 1:
    a.append(n)

print(nstr + ': ', end='')
print(*a)

Solution (Python):



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))))

Solution (Python):
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)))

Solution (Python):
import math

n = input()
prime = []

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)

Solution (Python):
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))

Solution (Python):
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=" ")


print(*factorize(n), sep=' ')

Solution (Python):
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),

Solution (Python):
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)))

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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))

Solution (Python):
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

Solution (Python):
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)))

Solution (Python):
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 = []
    
    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)
    
    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
    
    if not results:
        results = [start_num]
    return results


Primes = set()
if __name__ == '__main__':
    
    target_number = int(input())
    
    



    
    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))))

Solution (Python):



"""
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))

Solution (Python):



"""
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))

Solution (Python):
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))

Solution (Python):
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))

Solution (Python):
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))

Solution (Python):
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))

Solution (Python):
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)

Solution (Python):


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('')

Solution (Python):
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)

Solution (Python):
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))

Solution (Python):
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))))

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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 '')

Solution (Python):
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()

Solution (Python):
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)))

Solution (Python):
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)

Solution (Python):
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()

Solution (Python):
def is_prime(x):
    
    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()

Solution (Python):


import itertools
import sys, math, os


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))])))

Solution (Python):
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))))

Solution (Python):

import array
import math


def sieve_of_eratosthenes(end):
    """
    :type end: int
    :rtype: array.array
    """
    
    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
    
    prime_list = sieve_of_eratosthenes(upper_n)
    
    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))))

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):


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()

Solution (Python):
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)))

Solution (Python):
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))