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: Time Limit Exceeded

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

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: Time Limit Exceeded

Solution code:
def isPrime(x):
    if x == 2:
        return True

    if x < 2 or x % 2 == 0:
        return False
    i = 3
    xx = int(pow(x, 0.5))
    while i <= xx:
        if x % i == 0:
            return False
        i += 2
    return True

n = int(input())
rx = int(pow(n, 0.5))
l = rx+1
ps = []
for i in range(n):
    if isPrime(i):
        ps.append(i)
ans = []
i = 0
nn = n
ps.append(nn)
while n != 1:
    if n % ps[i] == 0:
        n //= ps[i]
        ans.append(ps[i])
    else:
        i += 1
print(str(nn)+":", ' '.join(map(str, ans)))

Submission status: Time Limit Exceeded

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())
    ans = []
    print("{}: ".format(n), end='')
    
    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)
        d += 2

    print(*ans)

solve()

Submission status: Time Limit Exceeded

Solution code:
def generate_prime(max_number):
    
    prime_list = []
    num = 0
#   count up to max number
    for i in range(max_number):
        num += 1

#       judge: 1
        if num == 1:
            continue

#       judge: 2
        if num == 2:
            #yield 2
            prime_list.append(num)
            continue

        k = 1
        ok = ''
        while k < num:
            k += 1
            if num % k == 0:
                break
            else:
                ok = 'X'

        if ok == 'X':
            #yield num
            prime_list.append(num)
                
    return prime_list

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

    count_d = {}
    factor_list = generate_prime(n)

    for factor in factor_list:#generate_prime(n)::

        while True:

            if n == factor:
                if str(factor) in count_d:
                    count_d[str(factor)] = count_d[str(factor)] + 1
                else:
                    count_d[str(factor)] = 1

                break

            if n % factor == 0:
                n = int(n / factor)
                if str(factor) in count_d:
                    count_d[str(factor)] = count_d[str(factor)] + 1
                else:
                    count_d[str(factor)] = 1

            else:
                break


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

    for factor in factor_list:

        if str(factor) in count_d:
            for count in range(int(count_d[str(factor)])):
                print('',factor,end='')
    print()

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math

def generate_prime(max_number):
    
    prime_list = []
    num = 0

#   count up to max number
    for i in range(max_number):
        num += 1

#       judge: 1
        if num == 1:
            continue

#       judge: 2
        if num == 2:
            #yield 2
            prime_list.append(num)
            continue

        if num > int(max_number / 2):
            prime_list.append(max_number)
            break

        k = 1
        ok = ''
        while k < num:
            k += 1
            if num % k == 0:
                break
            else:
                ok = 'X'

        if ok == 'X':
            #yield num
            prime_list.append(num)
                
    return prime_list

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

    #count_d = {}
    factor_list = generate_prime(n)

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

    for factor in factor_list:#generate_prime(n):

        counter = 0

        while True:

            if n == factor:
#                if str(factor) in count_d:
#                    count_d[str(factor)] = count_d[str(factor)] + 1
#                else:
#                    count_d[str(factor)] = 1
                counter += 1

                break

            if n % factor == 0:
                n = int(n / factor)
#                if str(factor) in count_d:
#                    count_d[str(factor)] = count_d[str(factor)] + 1
#                else:
#                    count_d[str(factor)] = 1
                counter += 1

            else:
                break


        for count in range(counter):
            print('',factor,end='')
    print()

'''
    for factor in factor_list:

        if str(factor) in count_d:
            for count in range(int(count_d[str(factor)])):
                print('',factor,end='')
    print()
'''

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def generate_prime(max_number):
    
    prime_list = []
    num = 0

#   count up to max number
    for i in range(max_number):
        num += 1

#       judge: 1
        if num == 1:
            continue

#       judge: 2
        if num == 2:
            yield 2
            #prime_list.append(num)
            continue

        if num > int(max_number / 2):
            yield max_number#prime_list.append(max_number)
            break

        k = 1
        ok = ''
        while k < num:
            k += 1
            if num % k == 0:
                break
            else:
                ok = 'X'

        if ok == 'X':
            yield num
            #prime_list.append(num)
                
    #return prime_list

def main():
	n = int(input())
	#factor_list = generate_prime(n)
	print(str(n)+':',end='')

	end = ''
	for factor in generate_prime(n):#factor_list:
		
		while True:

			if n % factor == 0:

				n = int(n / factor)
				print('',factor,end='')
				
				if n == 1:
					end = 'X'
					break
					
			else:
				break
		
		if end == 'X':
			break

# end of line						
	print()

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
def generate_prime(max_number):

	num = 0

# count up to max number
	for i in range(max_number):
		num += 1

# 	judge: 1
		if num == 1:
			continue

# 	judge: 2
		if num == 2:
			yield 2
			continue

		if num > int(max_number / 2):
			yield max_number
			break

		k = 1
		ok = ''
	
		while k < num:
			k += 1
			
			if k > int(num / 2):
				ok = 'X'
				break
				
			if num % k == 0:
				break
			else:
				ok = 'X'

		if ok == 'X':
			yield num

def main():
	n = int(input())
	#factor_list = generate_prime(n)
	print(str(n)+':',end='')

	end = ''
	for factor in generate_prime(n):#factor_list:
		#print(factor)
		
		while True:

			if n % factor == 0:

				n = int(n / factor)
				print('',factor,end='')
				
				if n == 1:
					end = 'X'
					break
					
			else:
				break
		
		if end == 'X':
			break

# end of line						
	print()

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import math

def generate_prime(max_number):
    
    prime_list = []
    num = 1

    if max_number == 1:
        return 0
    elif max_number >= 2:
        yield 2

#   count up to max number
    for i in range(3,max_number,2):
        num += 2

#       judge: 1
        if num == 1:
            continue

#       judge: 2
        if num == 2:
            yield 2
            continue

        if num % 2 == 0:
            continue

        if num > int(max_number / 2):
            yield max_number
            break

        k = 1
        ok = ''
        while k < num:
            k += 1
            if num % k == 0:
                break
            else:
                ok = 'X'

        if ok == 'X':
            yield num
                
def main():
    n = int(input())

    if n >= 2:
        print(str(n)+':',end='')

    for factor in generate_prime(n):
        
        end = ''
        while True:

            if n == factor:
                print('',factor,end='')
                break

            if n % factor == 0:
                n = int(n / factor)
                print('',factor,end='')
                if n == 1:
                    end = 'X'
                    break

            else:
                break
        if end == 'X':
            break

    print()

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math

def generate_prime(max_number):
    
    prime_list = []
    num = 1

    if max_number == 1:
        return 0
    elif max_number >= 2:
        yield 2

#   count up to max number
    for i in range(3,max_number,2):
        num += 2

#       judge: 1
        if num == 1:
            continue

#       judge: 2
        if num == 2:
            yield 2
            continue

        if num % 2 == 0:
            continue

        if num > int(max_number / 2):
            yield max_number
            break

        k = 1
        ok = ''
        while k < num:
            k += 1

            if k > num / 2:
                ok = 'X'
                break

            if num % k == 0:
                break
            else:
                ok = 'X'
                break

        if ok == 'X':
            yield num
                
def main():
    n = int(input())

    if n >= 2:
        print(str(n)+':',end='')

    for factor in generate_prime(n):
        
        end = ''
        while True:

#            if n == factor:
#                print('',factor,end='')
#                break

            if n % factor == 0:
                n = int(n / factor)
                print('',factor,end='')
                if n == 1:
                    end = 'X'
                    break

            else:
                break
        if end == 'X':
            break

    print()

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    oN = n   #originN
    Pn = primeNum(n)

    Fr = []   #Factoring
    i = 0
    while 1:
        if n == 1:
            break
        else:
            if n % Pn[i] == 0:
                n /= Pn[i]
                Fr.append(Pn[i])
            else:
                i += 1
                
    print(oN,end = "")
    print(":", end = " ")
    for x in range(len(Fr)):
        if x != len(Fr) - 1:
            print(Fr[x], end = " ")
        else:
            print(Fr[x])


def primeNum(num):
    Pn = [2]   #Prime numbers
    for x in range(3, num + 1, 2):
        c = 0
        for y in range(len(Pn)):
            if x % Pn[y] == 0:
                c = 1
                break
        if c == 0:
            Pn.append(x)
    return Pn

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
m = n
ary = []
for i in range(2,n):
    while True:
        if n % i == 0:
            ary.append(i)
            n /= i
        else:
            break
    if n == 1:
        break
    
if len(ary) == 0:
    print("{}: {}".format(m,m))
else:
    print("{}:".format(m),end="")
    for i in range(len(ary)):
        print(" {}".format(ary[i]),end="")
    print()

Submission status: Time Limit Exceeded

Solution code:
m=input();n=int(m);a=[];i=6
while n%2==0:a+=[2];n//=2
while n%3==0:a+=[3];n//=3
while i<n+2:
 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
print(m+':',*a)

Submission status: Time Limit Exceeded

Solution code:
m=input();n=int(m);s=n/2;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==int(m):a+=[m]
print(m+':',*a)

Submission status: Time Limit Exceeded

Solution code:
m=input();n=int(m);a=[];i=6
while n%2==0:a+=[2];n//=2
while n%3==0:a+=[3];n//=3
while i<int(m):
 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==int(m):a+=[m]
print(m+':',*a)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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 n>d+1:
    if s>d and n%d==0:
        p(d)
        n//=d
    else:d+=2
print(n)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
_N = N

ans = ''

def prime(m):
    p = [1]*m
    p[0] = 0
    sqrt = int(math.sqrt(m))
    for i in range(2,sqrt+1):
        for j in range(2,int(m/i)+1):
            p[i*j-1] = 0
    return([i+1 for i in range(m) if p[i] == 1 ])

for i in prime(N):
    while(N%i == 0):
        ans = ans + ' ' + str(i)
        N = N/i

print(str(_N)+':'+ans)

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
_N = N

ans = ''

def prime(m):
    p = [1]*m
    p[0] = 0
    sqrt = int(math.sqrt(m))
    for i in range(2,sqrt+1):
        for j in range(2,int(m/i)+1):
            p[i*j-1] = 0
    return([i+1 for i in range(m) if p[i] == 1 ])

for i in prime(N):
    while(N%i == 0):
        ans = ans + ' ' + str(i)
        N = N/i
    if N == 1:
        break

print(str(_N)+':'+ans)

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
_N = N

ans = ''

for i in range(2,N+1):
    while(N%i == 0):
        ans = ans + ' ' + str(i)
        N = N/i
    if N == 1:
        break

print(str(_N)+':'+ans)

Submission status: Time Limit Exceeded

Solution code:
X  = int(input())
temp = X
ret = repr(X) + ':'
for cnt in range(2, X+1):
    while temp % cnt == 0:
        temp = temp / cnt
        ret += ' ' + repr(cnt)
    cnt += 1
print(ret)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    original_n = n
    primes = []

    factor = 2
    while True:
        if n == 1:
            break

        if n % factor == 0:
            n //= factor
            primes.append(factor)
            continue
        else:
            factor += 1

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



main()

Submission status: Memory Limit Exceeded

Solution code:
N = int(input())
n = N
mydict = {}
L = []
cnt = 0

for i in range(2, n+1):
    while n%i == 0:
        n = n/i
        cnt += 1
    mydict[i] = cnt
    cnt = 0

for i in range(2, N+1):
    if i in mydict:
        for j in range(mydict[i]):
            L.append(i)

print(str(N) + ': ' + ' '.join(map(str, L)))

Submission status: Memory Limit Exceeded

Solution code:
from collections import defaultdict

def sieve_of_eratosthenes(ub):
    # O(n loglog n) implementation.
    # returns prime numbers <= ub.
    if ub < 2:
        return []
    prime = [True]*(ub+1)
    prime[0] = False
    prime[1] = False
    p = 2
    while p*p <= ub:
        if prime[p]:
            # don't need to check 2p ~ (p-1)p (they've already been checked).
            for i in range(p*p, ub+1, p):
                prime[i] = False
        p += 1
    return [i for i in range(ub+1) if prime[i]]
        
def factorize(n):
    result = defaultdict(int)
    for p in sieve_of_eratosthenes(n):
        while n % p == 0:
            n = n // p
            result[p] += 1
    return result

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

Submission status: Memory Limit Exceeded

Solution code:
from collections import defaultdict

def sieve_of_eratosthenes(ub):
    # O(n loglog n) implementation.
    # returns prime numbers <= ub.
    if ub < 2:
        return []
    prime = [True]*(ub+1)
    prime[0] = False
    prime[1] = False
    p = 2
    while p*p <= ub:
        if prime[p]:
            # don't need to check 2p ~ (p-1)p (they've already been checked).
            for i in range(p*p, ub+1, p):
                prime[i] = False
        p += 1
    for i in range(2, ub+1):
        if prime[i]:
            yield i
        
def factorize(n):
    result = defaultdict(int)
    for p in sieve_of_eratosthenes(n):
        while n % p == 0:
            n = n // p
            result[p] += 1
    return result

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

Submission status: Memory Limit Exceeded

Solution code:
n = input()
l = []
l += [str(n)+":"]
while 1:
    if n == 1: break
    for i in range(2,n+1):
        if n % i == 0:
            n /= i
            l += [i]
            break
print " ".join(map(str,l))

Submission status: Memory Limit Exceeded

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

Submission status: Memory Limit Exceeded

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)
        else:
            i += 2
    if n > 1:
        a.append(n)
    return a
print(str(n)+":",*function(n))

Submission status: Memory Limit Exceeded

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

while n>1:
	for i in range(2,N+1):
		if n%i==0:
			n=n/i
			a.append(str(i))
			break

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

Submission status: Accepted

Solution code:
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)))

Submission status: Accepted

Solution code:
# python template for atcoder1
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))))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)
    # nのすべての素因数を見つける
    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))

Submission status: Accepted

Solution code:
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))))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)))

Submission status: Accepted

Solution code:
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))))

Submission status: Accepted

Solution code:
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)])

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)