质数分解问题

用线性筛进行素数筛法，过程种记录每一个数的最小质因子

筛选质因子时，不断对质因子进行除法，再对得到的数继续取最小质因子，直至得到一个数的所有质因子

这个过程主要会用在算数基本定理种

python版本

def getPrimes(N):
    for i in range(2,N+1):
        if vis[i] == False:
            primes.append(i)
            minp[i] = i
        j = 0
        while primes[j]*i <= N:
            vis[primes[j]*i] = True
            minp[primes[j]*i] = primes[j]
            if i % primes[j] == 0:
                break
            j += 1


N = 1000100
vis = [0]*(N + 1)
minp = [0]*(N + 1)
primes = []
getPrimes(N)

n = int(input())

fact = []
countPrimes = [0]*(N + 1)

for x in range(2,n+1):
    while x > 1:
        curPrime = minp[x]
        fact.append(curPrime)
        while x % curPrime == 0:
            countPrimes[curPrime] += 1
            x //= curPrime

for i in range(2,len(countPrimes)):
    if countPrimes[i]:
        print(i,countPrimes[i])