小南解题---蓝桥杯算法提高VIP-质因数2---121ms

#可过蓝桥oj

'''zgn946

0:17 2022/5/9'''

def is_prime(num):  #素数判断

    if num==2 or num==3:

        return True

    if num%6!=1 and num%6!=5:

        return False

    for i in range(5,int(num**0.5)+1,6):

        if num%i==0 or num%(i+2)==0:

            return False

    return True 

#合数分解

def a(num, list):

    for i in list:

        if num % i == 0:

            return i

#

def fenjie(num):

    global ct

    global ls

    if is_prime(num):  #是素数直接返回

        ct+=1

        aa.append(num)

        return str(num)

    else: #不是素数，进行下一步

        yinzi = a(num, ls)

        ct+=1

        aa.append(yinzi)

        return    str(yinzi) + ' ' + fenjie(num // yinzi)

#

#所给区间的素数都放进一个列表

ls= []

aa=[]

n =eval(input().strip())

for j in range(2, n + 1):

    if is_prime(j):

        ls.append(j)

ct=0

fenjie(n)

#print(str(n) + '=' + fenjie(n))

for i in aa:

    print(i,end=' ')

print()

print(ct)