エラトステネスの篩による素数判定・素因数分解・約数列挙

エラトステネスの篩

$N$ 以下の数に対して、以下のことができる。

$O(N\log\log N)$ 　前処理

$O(1)$ 　　　　　　素数判定
$O(\log N)$ 　　　　素因数分解
$O(\log N)$ 　　　　約数の個数　 $d(N)$
$O(\log N)$ 　　　　約数の総和　 $\sigma (N)$
$O(d(N))$ 　　　　　約数列挙

_n=10**5        #最大値
sieve=list(range(_n+1))
sieve[0]=sieve[1]=-1
for i in range(2,int(_n**0.5)+1):
    if sieve[i]==i:
        for j in range(i*i,_n+1,i):
            if sieve[j]==j:
                sieve[j]=i

def isprime(x):
    return sieve[x]==x

def factorization(x):   #O(logN)
    ans=[] 
    while x>1:
        p=sieve[x]
        ans.append([p,0])
        while sieve[x]==p:
            x//=p
            ans[-1][-1]+=1
    return ans

def d(x):              #O(logN) 約数の個数
    ans=1
    while x>1:
        p=sieve[x]
        cnt=0
        while sieve[x]==p:
            x//=p
            cnt+=1
        ans*=cnt+1
    return ans

def sigma(x):          #O(logN) 約数の総和
    ans=1
    while x>1:
        p=sieve[x]
        cnt=0
        res=1
        while sieve[x]==p:
            res*=p
            cnt+=res
            x//=p
        ans*=cnt+1
    return ans

def divisors(x):    #O(d(x)) 約数の列挙
    ans=[1]
    while x>1:
        p=sieve[x]
        t=len(ans)
        while sieve[x]==p:
            for i in ans[-t:]:
                ans.append(i*p)
            x//=p
    #ans.sort()
    return ans

使い方

#素数判定
print(isprime(1))           #   >>False
print(isprime(2))           #   >>True

#素因数分解
print(factorization(12))    #   >> [[2, 2], [3, 1]]
print(factorization(1024))  #   >> [[2, 10]]

#約数の個数
print(d(18))                #   >> 6
print(d(169))               #   >> 3

#約数の総和
print(sigma(18))            #   >> 39
print(sigma(169))           #   >> 183

#約数の列挙
print(divisors(18))         #   >> [1, 2, 3, 6, 9, 18]
print(divisors(169))        #   >> [1, 13, 169]

例題
ABC117E

参考