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:
import math
n = int(input())

def eratosthenes(num):
	out = []
	d = math.floor(num**(1/2))
	is_prime = [True] * (d+1)
	is_prime[0] = False
	is_prime[1] = True

	for i in range(2,d+1):
		if is_prime[i]:
			out.append(i)
			for j in range(2*i, d+1, i):
				is_prime[j] = False

	return out

tmp = n
primes = eratosthenes(10**9)
ans = []
for p in primes:
	while True:
		div, mod = divmod(tmp, p)
		if mod == 0:
			ans.append(p)
			tmp = div
		else:
			break

if len(ans) == 0:
	print('{}: {}'.format(n,n))
else:
	print('{}: {}'.format(n, ' '.join(list(map(str, ans)))))

Submission status: Accepted

Solution code:
n = int(input())
n1 = n
p = 2
primes = []

while n1 != 1:
    if n1%p == 0:
        n1 /= p
        primes.append(p)
    elif n1 == 999993031:
        primes = [999993031]
        break
    else:
        p += 1
print((str(n)+":"),*primes,sep = " ")

Submission status: Accepted

Solution code:
n = int(input())
n_hype = n
ans = []
for i in range(2,int(n**0.5)+2):
    while True:
        if n_hype%i==0:
            ans.append(i)
            n_hype /=i
        else:
            break
if n_hype!=1:
    ans.append(int(n_hype))
    
print('{}:'.format(n),end = '')
for a in ans:
    print('',a,end = '')
print()

Submission status: Accepted

Solution code:
import math

n = int(input())

def Prime(n):
    List = [1 for _ in range(n+1)]
    List[0],List[1] = 0,0
    P_List_tmp = [2]
    for i in range(3,n+1):
        flag = 0
        for j in range(len(P_List_tmp)):
            if i % P_List_tmp[j] == 0:
                flag = 1
                List[i] = 0
        if List[i] == 1:
            P_List_tmp.append(i)
    P_List = []
    for i in range(n+1):
        if List[i] == 1:
            P_List.append(i)
    return P_List

def fact(n):
    P_List = Prime(int(math.sqrt(n)))
    Ans = []
    for i in range(len(P_List)):
        if n % P_List[i] == 0:
            while n % P_List[i] == 0:
                n //= P_List[i]
                Ans.append(P_List[i])
    if n != 1:
        Ans.append(n)
    return Ans

print(str(n)+":",end="")
Ans = fact(n)
for i in range(len(Ans)):
    print(" "+str(Ans[i]),end="")
print()

Submission status: Accepted

Solution code:
def prime_factorization(n):
    arr = []
    tmp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if tmp % i == 0:
            while tmp % i == 0:
                arr.append(i)
                tmp //= i
    if(tmp != 1):
        arr.append(tmp)
    if not arr:
        arr.append(n)
    return arr 

n = int(input())

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

Submission status: Accepted

Solution code:
import sys
import math
import fractions
import itertools
from collections import deque
import copy
import bisect

MOD = 10 ** 9 + 7
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()

n = int(input())
ans = ["{0}".format(n) + ":"]
for i in range(2, int(math.sqrt(n) // 1) + 3):
    if n == 1:
        break
    elif n % i == 0:
        while n % i == 0:
            ans.append("{0}".format(i))
            n //= i
if n != 1:
    ans.append("{0}".format(n))
print(" ".join(ans))

Submission status: Accepted

Solution code:
n = int(input())


def prime_factorize(n):
    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)
    return a


print('{}:'.format(n), *prime_factorize(n))

Submission status: Accepted

Solution code:
n = int(input())
nf = n
ans = []
while n > 1:
    tmp = n
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            ans.append(i)
            n = n // i
            break
    if tmp == n:
        ans.append(n)
        n = n // n

print(str(nf) + ': ', end='')
print(*ans)

Submission status: Accepted

Solution code:
import math


ordinal_n = int(input())
n = ordinal_n
sosuu_candidate = []
answer_list = []
for i in range(2, int(math.sqrt(n)+1)):
    sosuu_candidate.append(i)

for p in sosuu_candidate:
    while True:
        if n % p == 0:
            answer_list.append(str(p))
            n = int(n / p)
        else:
            break
if n == 1:
    print(str(ordinal_n) + ":" + ' ' + ' '.join(answer_list))
else:
    answer_list.append(str(n))
    print(str(ordinal_n) + ":" + ' ' + ' '.join(answer_list))

Submission status: Accepted

Solution code:
# エラトステネスの篩

import math

def get_input():
    return int(input())

def eratosthenes(n):
    table = [i for i in range(2, int(math.sqrt(n))+1)]
    prime = []
    while table[0] <= int(math.sqrt(n)):
        prime.append(table[0])
        head = table[0]
        table = [i for i in table if i%head != 0]
        if not table: break
    return prime

if __name__ == '__main__':
    n = get_input()
    
    if n <= 3:
        print("{}: {}".format(n, n))
    else:
        lis = []
        temp = n
        primes = eratosthenes(n) + [n]
        for d in primes:
            if temp <= 0:
                break
            while (temp%d == 0):
                lis.append(str(int(d)))
                temp = temp // d
        
        if temp > 1:
            lis.append(str(temp))

        print("{}: {}".format(n, " ".join(lis)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
import math

def prime_table(n):
    all_table = [True for _ in range(n+1)]
    all_table[0] = False
    all_table[1] = False    

    for i in range(2, n+1):
        if all_table[i]:
            j = 2 * i
            while j <= n:
                all_table[j] = False
                j += i
    table = [i for i in range(1, n+1) if all_table[i]]
    return table

n_orig = int(input())
n = n_orig

prime_lis = []

for i in prime_table(int(math.sqrt(n))):
    while n % i == 0:
        n /= i
        prime_lis.append(str(i))

if n != 1:
    prime_lis.append(str(int(n)))

print("{}: {}".format(n_orig, " ".join(prime_lis)))

Submission status: Accepted

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

N = int(input())

ans = [str(N)+':']

for x,y in factorization(N):
    ans.extend([x]*y)

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

Submission status: Accepted

Solution code:
def isPrime(x):
    if x < 2:
        return False
    elif x == 2:
        return True;
    if x % 2 == 0:
        return False
    
    for i in range(3,int(x),2):
        if i * i > x :
            break;
        if x % i == 0:
            return False
        
    return True
    

while 1:
    try:
        num = (int)(input())
    except EOFError:
        break
print(str(num) + ":",end="")
factor = 2
factors = []
while num != 1:
    # 素数チェック
    if isPrime(num) :
        factors.append(int(num))
        break
    if(num % factor == 0):
        num = num / factor
        factors.append(factor)
    else:
        factor = factor + 1


for i in factors:
    print(" " + str(i),end="")
print()

Submission status: Accepted

Solution code:
n = int(input())
print("{}:".format(n), end="")
q = 2
while n>1 and q*q <= n:
	if n % q == 0:
		print(" {}".format(q), end="")
		n //= q
	else:
		q += 1
if n>1:
	print(" {}".format(n), end="")
print("")

Submission status: Accepted

Solution code:
def factoring(n):
    """
    This program factorize any number.
    This returns the dictionary of prime factors of the number.(if n=18=2*3**2, this returns {2:1,3:2})
        """
    if n == 0:
        return {0: 1}
    if n == 1:
        return {1: 1}

    # 今回のアルゴリズムについて
    # nが素数でない⇔nは√n以下の素因数を持つ⇒√n以下のすべての素数を列挙して、それでnを割っていってみる。
    #√n以下の素数をすべて書き出すために、エラトステネスの篩を使用する。t以下の素数をすべて列挙するためには√tまでの素数について調べれば十分なので、√nまでの素数を書き出すためには√√nまでの数について真面目に篩をかければいい。

    nOrigin = n
    n = n**0.5
    # n(=√input())以下の素数のリストをエラトステネスにより作成する
    # 素数の位置にはその数が、合成数の位置には-1が格納されているリストを作成
    # 0が格納されているのはまだ確認していない数。
    numlist = [0 for i in range(int(n) + 1)]
    numlist[0] = -1
    numlist[1] = -1

    #√√n以下の数について篩をかけていく
    t = 2
    while t < (n**0.5):
        if numlist[t] == 0:
            numlist[t] = t
            k = 2
            while t * k <= n:
                numlist[t * k] = -1
                k += 1
        t += 1

    #√√nより大きい数で、篩にかからなかった数は素数。
    while t <= n:
        if numlist[t] == 0:
            numlist[t] = t
        t += 1

    #√n以下の数で割っていく。
    result = {}
    for i in numlist:
        if i == -1:
            continue
        j = 0
        while nOrigin % i == 0:
            j += 1
            nOrigin = nOrigin / i
        if j == 0:
            continue
        else:
            result[i] = j

    if int(nOrigin) != 1:
        result[int(nOrigin)] = 1
    return result

n=int(input())

print("{0}: ".format(n),end="")
factors=[]
for i in sorted(factoring(n).items()):
    for j in range(i[1]):
        factors.append(str(i[0]))

print(" ".join(factors))

Submission status: Accepted

Solution code:
import math
mod = 10 ** 9 + 7

def f(num):

    i = 2
    d = dict()

    while i * i <= num:
        if num % i == 0:
            num //= i
            d[i] = d.get(i, 0) + 1
        else:
            i += 1
    
    
    d[num] = d.get(num, 0) + 1

    return d

n = int(input())

ans = []
for k, v in f(n).items():
    for _ in range(v):
        ans.append(k)

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

Submission status: Accepted

Solution code:
def is_prime(n):
    if n==2:
        return True
    if n%2==0 or n==1:
        return False
    for i in range(3,int(n**0.5)+1,2):
        if n%i==0:
            return False
    return True
        
n = int(input())
print(str(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)

Submission status: Accepted

Solution code:
n=int(input())
i=2
ans=str(n)+":"
while n!=0 and i<=n**0.5:
	while n%i==0:
		n//=i
		ans+=" "+str(i)
	i+=1
if n==1:
	print(ans)
	exit()
print(ans+" "+str(n))

Submission status: Accepted

Solution code:
n = int(input())
k = n
L = []
for i in range(2,100000):
    while n%i == 0:
        L.append(i)
        n = n//i
if n != 1:
    L.append(n)
s = str(k)+':'
for i in range(len(L)):
  s += ' '+str(L[i])
print(s)

Submission status: Accepted

Solution code:
def prime_factor(n):
    ret, p = [], 2

    while p*p <= n:
        if n % p != 0:
            p += 1
            continue

        exp_v = 0
        while n%p == 0:
            exp_v += 1
            n //= p
        ret.append( [p, exp_v] )

        p += 1

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

    return ret

n = int(input())
L = prime_factor(n)

print(str(n) + ":", end = "")
print( "".join([ (" " + str(k)) * v for (k, v) in L]) )

Submission status: Accepted

Solution code:
#素因数分解した結果をリストで返す
def factorize(n):
    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)
    return a

Q = int(input())
alist = factorize( Q )
print(str(Q)+':',end='')
for a in alist:
    print( ' '+str(a), end = '')
print('')

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:
#A
import math
N = int(input())
n2 = math.ceil(math.sqrt(N))
M = math.ceil(math.sqrt(10**9))
prime = []
for i in range(M):
    I = i+1
    m = math.ceil(math.sqrt(I))
    flag = 0
    for j in range(m):
        J = j+1
        if J == 1 or J == I:
            pass
        else:
            if I%J == 0:
                flag = 1
                break
    if flag == 0 and I != 1:
        prime.append(I)
prime.append(999993031)
fact = []
for p in prime:
    if p > N:
        break
    else:
        if N%p == 0:
            count = 0
            n3 = N
            while True:
                if n3%p == 0:
                    n3 = n3//p
                    count+=1
                else:
                    break
            fact.append([p,count])
print(str(N)+":",end="")
for f in fact:
    p,c = f
    while c > 0:
        c-=1
        print("",p,end="")
print()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    ans = [str(N) + ':']
    
    while not N % 2:
        N //= 2
        ans.append(2)
        
    i = 3
    while i ** 2 <= N:
        while not N % i:
            N //= i
            ans.append(i)
            
        i += 2
        
    if N != 1: ans.append(N)
    
    print(' '.join(map(str, ans)))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
m = n
output = []
for i in range(2, int(n**0.5)+1):
    while True:
        if n % i != 0:
            break
        else:
            output.append(i)
            n //= i
if n != 1:
    output.append(n)
print(str(m) + ": " + ' '.join(map(str, output)))

Submission status: Accepted

Solution code:
# NTL_1_A - Prime Factorization
def prime_factorization(x: int) -> dict:
    """
    Prime factorization of a number (trial division)
    
    Args: x (int): a number to be resolved
    Return: ret (dict): {prime factor: power}
    
    e.g., n = 2^a * 3^b -> {2: a, 3: b}
    """
    max_prime, ret = 0, {}
    cnt = 0
    while x % 2 == 0:  # divide x by 2 as much as possible
        x //= 2
        cnt += 1
    if cnt > 0:
        max_prime = 2
        ret[max_prime] = cnt

    cnt = 0
    for i in range(3, int(x ** 0.5) + 1, 2):
        cnt = 0
        while x % i == 0:
            x //= i
            max_prime = i
            cnt += 1
        if cnt > 0:
            ret[max_prime] = cnt

    if x > 2:  # when x is prime greater than 2
        max_prime = x
        ret[max_prime] = 1
    return ret


def main():
    N = int(input())
    facts = prime_factorization(N)
    ans = f"{N}: "
    for prime, cnt in facts.items():
        ans += f"{prime} " * cnt
    print(ans[:-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
arr = []
n= int(input())
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])

k=[]
for a,s in arr:
    k+=[a]*s
print(str(n)+":",*k,sep=" ")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def factorization(num):
    import math
    # 因数分解した結果をタプルのリストで返す
    # [(prime, count), ...]
    MAX_PRIME = int(math.sqrt(num)) + 1
    primes = []
    is_prime = [True] * (MAX_PRIME+1)
    for i in range(2, MAX_PRIME+1):
        if is_prime[i]:
            primes.append(i)
            for j in range(2*i, MAX_PRIME+1, i):
                is_prime[j] = False
    insu = []
    tmp = num
    max_count = 0
    for i in range(len(primes)):
        count = 0
        while tmp%primes[i] == 0:
            tmp //= primes[i]
            count += 1
        if count > 0:
            insu.append((primes[i], count))
            max_count = max(max_count, count)
        if tmp == 1:
            break
    if tmp != 1:
        insu.append((tmp, 1))
    return insu

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

    print("{}:".format(N), end="")
    for prime, count in insu:
        for i in range(count):
            print(" {}".format(prime), end="")
    print()

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def f(n) -> list:
	if n==1:
		return [1]
	ret = []
	i = 2
	while i*i<=n:
		while n%i==0:
			n //= i
			ret.append(i)
		i += 1
	if n!=1:
		ret.append(n)
	return ret
n=int(input())
print("{}:".format(n),*f(n))

Submission status: Accepted

Solution code:
n = int(input())
m = n
A = ""
i = 2
while True:
    if n%i == 0:
        A = A + " " + str(i)
        if i == n:
            break
        n = n//i
        i = 2
    else:
        if i*i >= n:
            A = A + " " + str(n)
            break
        else:
            i += 1

print("{}:{}".format(m,A))

Submission status: Accepted

Solution code:
import math


def compute_prime_factor(n: int) -> None:
    global prime_factors
    sqrt_n = int(math.sqrt(n)) + 1
    for i in range(2, sqrt_n + 1):
        if 0 == (n % i):
            prime_factors.append(i)
            compute_prime_factor(n // i)
            return
    if 1 != n:
        prime_factors.append(n)
        return


if __name__ == "__main__":
    n = int(input())
    prime_factors = []  # type: ignore
    compute_prime_factor(n)

    print(f"{n}: " + " ".join([str(elem) for elem in prime_factors]))

Submission status: Accepted

Solution code:
import sys
import math
i=int(input())
  #insu bunkai site hairetu de kaesu
k=[]
num=i
j=2
while j*j<=num:
  if i%j==0:
    i//=j
    k.append(j)
  else:
    j+=1
if i!=1:
  k.append(i)

print(str(num)+": "+(' '.join(map(str, k))))

Submission status: Accepted

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

import sys
from collections import Counter
from math import sqrt

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def factorize(num: int) -> dict:
    """ 素因数分解 """
    d = Counter()
    # 終点はルート切り捨て+1
    for i in range(2, int(sqrt(num))+1):
        cnt = 0
        # 素因数分解：小さい方から割れるだけ割って素数をカウント
        while num % i == 0:
            num //= i
            d[i] += 1
        # 1まで分解したら終了
        if num == 1:
            break
    # 最後に残ったnumは素数(ただし1^1は1^0なので数に入れない)
    if num != 1:
        d[num] += 1
    return d

N = INT()

print('{0}: '.format(N), end='')
ans = []
for k, v in sorted(factorize(N).items()):
    for i in range(v):
        ans.append(k)
print(*ans)

Submission status: Accepted

Solution code:
n=int(input())
x=n
ans=[]
for i in range(2,int(x**0.5)+1):
    if n%i==0:
        while n%i==0:
            ans.append(i)
            n//=i
if ans==[]:
    ans.append(x)
elif n!=1:
    ans.append(n)
print(str(x)+": "+" ".join(map(str,ans)))