[백준] 1124 - 언더프라임
문제
문제 링크 : https://www.acmicpc.net/problem/1124
문제풀이
구하고자 하는 것 : 두 정수 A와 B 사이의 숫자 중 소인수분해하여 구한 소수의 목록 개수가, 소수인 수의 개수
- is_prime 함수 : A부터 B까지의 수에 대해 가지고 있는 소수와 그 개수의 소수 여부를 전부 파악해야 하므로, is_prime 이라는 함수를 따로 만들어 변수 x에 대한 소수 여부를 반환하도록 하였다.
- 에라토스테네스의 체 : 이때, 소수 여부를 파악하기 위해 시간 복잡도가 작은 에라토스테네스의 체를 이용하였다.
- counts 배열 : 에라토스테네스의 체를 조금 변형하여, 합성수인 경우, 소인수분해했을 때 몇 개의 소수(중복 가능)를 포함하는지 counts 배열에 기록했다.
- prime 배열 : 소수일 경우 prime 배열에 기록하며, 이후 소수의 개수가 소수인지 아닌지 파악할 때 재사용하였다.
개수의 소수 여부를 판단하기 위해 A의 최솟값인 2부터 B까지 is_prime 함수를 적용했다. is_prime 함수에서 x에 대해 소수가 아닌 경우, 첫 번째로 나누는 값 i는 반드시 소수이다.
이때,
x//i 값이 소수인 경우 counts 배열의 값이 0이므로 i와 x//i 로 소인수분해되므로 counts[x] 값은 2이다.
x//i 값이 합성수인 경우 x//i는 x보다 반드시 작으므로 이미 counts 배열에 기록되어 있기 때문에 i와 x//i를 소인수분해한 소수의 수를 더해 counts[x]에 갱신(DP)한다.
이후 2부터 B까지의 수에 대하여 소인수분해한 소수의 수를 counts에 모두 기록하면, 범위 [a,b]에 대해 counts[i] 값이 prime 리스트에 포함되는지 여부를 확인하여 그 수를 센다.
에라토스테네스의 체
에라토스테네스의 체는 어떤 수 x에 대해 x가 소수인지 확인하기 위해, 2보다 크고 x보다 작은 수로 x를 차례대로 나누어보아, 나눠지는 경우에는 합성수, 나눠지지 않는 경우에는 소수로 판단하는 방법이다. 이때, 모든 합성수에 대해 소인수분해되어 나눠지는 두 값 중 하나는 반드시 x**(1/2) 이하의 값을 가진다. 따라서 x는 2부터 x**(1/2)까지의 수에 대해서만 나눠지는지 여부를 확인하면 되므로 시간복잡도 O(n**(1/2))를 갖는다.
출처 :
코드
import math
a,b=map(int,input().split(' '))
prime=[]
counts=[0 for _ in range(b+1)]
def is_prime(x):
end = int(math.sqrt(x))
if x<=3:
return True
for i in range(2,end+1):
if x%i==0:
if x//i in prime:
counts[x]=2
else:
counts[x]=1+counts[x//i]
return False
return True
for i in range(2,b+1):
if is_prime(i):
prime.append(i)
answer=0
for i in range(a,b+1):
if counts[i] in prime:
answer+=1
print(answer)