【HJ6】质数因子

https://blog.nowcoder.net/n/038590a04751480789589773f54a0cb0?f=commentHJ6
Trick: 比如说求9以内的质数个数,那么只要划掉sqrt(9)以内的质数倍数,剩下的即全为质数. 所以在划去倍数的时候也是从i*i开始划掉,而不是i+i.

解法一：

import sys


for line in sys.stdin:
    line = line.strip()
    
    n = int(line)
    
    i = 2
    while i <= n:
        while n % i == 0:
            print(i, end=' ')
            n = n // i
        i += 1

解法二：优化版本

import sys


for line in sys.stdin:
    line = line.strip()
    
    n = int(line)
    
    i = 2
    while i <= n and i*i <= n:
        while n % i == 0:
            print(i, end=' ')
            n = n // i
        i += 1
    if n != 1:
        print(n, end=' ')