백준 15520 - Prime-Factor Prime [Python]

https://www.acmicpc.net/problem/15520

15520번: Prime-Factor Prime

[사용한 것]

에라토스테네스의 체

 

1. 나누려는 소수 \(i\)의 범위 정하기

어떤 수가 소수인지 확인하는 방법 중, \( \sqrt{N} \)까지의 수만 확인하는 방법이 있다.

이를 이용하여, 문제의 조건인 "r <= 10억" 이라는 조건에 따라서 나눌 소수 \(i\)는 2부터 33000사이의 값으로 정할 수 있다. 왜 이렇게 하는지는 아래 과정을 보면 알것이다

 

 

2. \(i\)의 배수가 구간 \( [l, r] \) 내에 존재하는지 확인하기

부등식 \( l \leq k \times i \leq r \)를 만족하는 자연수 k가 존재하는지를 확인하면 된다.

 

 

3. 소인수의 개수 갱신하기

\(i\)의 배수가 존재한다면, 위의 부등식을 만족하는 k의 최솟값부터 쭉 갱신해주면 된다.

수 \(k \times i \)를 계속 i로 나눠주면 된다.

 

모든 과정이 다 끝났을 때, (33000 이상의 소수)\(\times x\) 꼴의 수는 아직 1이 되지 않은 상태일 것이고, 33000 이상의 소수로 남아있을 것이다. 따라서 1이 아닌 수가 있다면 '그 수의 소인수인 약수의 개수'에 +1을 해주면 된다.

 

4. 답 찾기

이제 다 끝났다. 소인수인 약수의 개수들을 쭉 훑으며 소수인지 판별하면 된다.

 

아래는 파이썬으로 작성한 코드이다.

import sys
input = sys.stdin.readline
 
#input
def mip(): return map(int, input().split())
 
#prime
def isPrime(x):
    if x<=1: return False
    for i in range(2, int(x**0.5)+1):
        if x%i==0:
            return False
    return True
 
############### Main! ###############
 
l, r = mip()
a = [i for i in range(l, r + 1)]
c = [0 for _ in range(1000001)]
 
for i in range(2, 33001):
    if not isPrime(i):
        continue
    lo = (l + i - 1) // i
    hi = r // i
    if lo > hi:
        continue
    for j in range(lo, hi + 1):
        while a[i * j - l] % i == 0:
            a[i * j - l] //= i
            c[i * j - l] += 1
for i in range(r - l + 1):
    if a[i] != 1:
        c[i] += 1
 
ans = 0
for i in c:
    if isPrime(i):
        ans += 1
print(ans)
 
######## Priest W_NotFoundGD ########