백준 1124번 파이썬 코드

문제

자연수 X를 소인수 분해 하면, 곱해서 X가 되는 소수의 리스트가 나온다. 12는 2*2*3이고, 1은 소수가 아니다. 이때, X가 언더프라임이기 위한 조건은 소인수 분해 했을 때, 나오는 소수의 개수가 소수일 때이다. 예를 들어, 12는 언더프라임이다. 그 이유는 나오는 소수의 개수가 3개이기 때문이다. A와 B가 주어졌을 때, A보다 크거나 같고, B보다 작거나 같은 언더프라임의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 A와 B가 주어진다. A는 B보다 작거나 같고, A와 B는 100,000보다 작거나 같고, 2보다 크거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

 

 

접근방법1. 에라토스테네스의 체 + 필터 조건

처음의 접근은 에라토스테네스의 체로 소수판정을 하여, 미리 100,000까지에 대한 소수 판정을 다 해둔다. 그 후, a~b 사이의 값을 각각 소인수분해를 해서, 분해한 소수의 갯수가 소수인지를 확인하는 절차를 반복했다. 이 경우, 당연하게도 시간초과가 발생했다.

처음에 나는 에라토스테네스의 체가 효율적이지 못하기 때문에 시간초과가 발생한다고 생각을 하고, 인터넷에서 여러가지 방법을 찾아보았고, 이를 적용했는데 에라토스테네스의 체가 시간초과를 해결하는 키가 되지는 않았다. 

다른 방법은 필터링을 하는 방법이었다. a~b 사이의 수중 소수인 수는 이미 소인수 분해를 할 경우 딱 1이라는 숫자만 나온다. 그런데 이 때, 1은 소수가 아니기 때문에 소인수 분해를 할 필요가 없다. 이 조건을 감안해서 코딩을 할 경우, pypy3로 4628ms의 시간이 필요하다. 

import sys
def sol(num) :
    answer = num
    my_li_cnt = 0
    sosu_cnt = 0
    while answer != 1 :
        for i in range(2,answer+1) :
            if answer % i == 0 :
                answer = answer // i
                my_li_cnt +=1
                if d[i] == True :
                    sosu_cnt +=1
                break
    if sosu_cnt == my_li_cnt and d[sosu_cnt] == True :
        return True
    else :
        return False

a,b = map(int,sys.stdin.readline().split())
d = [True for _ in range(100001)]
d[1] = False


for n in range(2,100000+1) :
    if d[n] :
        for k in range(n,100000+1) :
            if n * k > 100000 :
                break
            d[n*k] = False
    if n * (n+1) > 100000 : 
        break



answer_cnt = 0
for i in range(a,b+1) : 
    if i != 1 :
        if d[i] == False:
            if sol(i) :
                answer_cnt +=1


print(answer_cnt)

 

접근방법2. 에라토스테네스의 체 + 다이나믹 프로세스

다른 정답자들이 푼 시간을 확인해보니 4600ms가 아니라 수백ms로 끊는 것을 확인했다. 에라토스테네스의 체는 더 줄일 수 있기 때문에, 소인수분해 자체를 더 줄여야 했다. 소인수 분해를 하지 않는 대신, 소인수 분해에 '에라토스테네스의 체'의 아이디어를 적용하여 다이나믹 프로세스를 진행했다.

먼저 dd라는 메모이제이션을 할 리스트를 만들어준다. 초기값은 1로 넣어준다. 이 이유는 소인수 분해가 되지 않을 경우, 자기 자신의 값을 가지기 때문에 최소한 '1'이라는 값을 가진다는 의미다. 

이후, 2부터 b+1까지 숫자에 대해서 이중 For문으로 메모리제이션을 돌렸다. 먼저 2라는 숫자에 대해서 살펴본다. 2의 소인수 분해 중 소수 갯수는 당연하게도 현재 1이다.

- 2에 2를 곱해줄 경우 : 소수인 2가 곱해지기 때문에 결과물인 4는 2의 소수 갯수 '1'에 1개가 더해진 2가 됨
- 2에 3을 곱해줄 경우 : 소수인 3이 곱해지기 때문에 결과물인 6은 2의 소수 갯수 '1'에 1개가 더해진 2가 됨 
...
- 4에 3을 곱해줄 경우 : 소수인 3이 곱해지기 때문에 결과물인 12는 4의 소수 갯수 '2'에 1개가 더해진 3이 됨.

위의 프로세스를 O(N^2)에 대해서 반복하게 되면, dd의 결과물이 다 채워진다. dd 리스트를 a~b부터 소수인지 아닌지 확인해서, 그 수를 카운트해서 출력하는 것으로 문제의 풀이속도는 매우 간단해진다. 풀이속도는 4600ms → 120ms로 감소한다.

import sys

a,b = map(int,sys.stdin.readline().split())
d = [True for _ in range(100001)]
d[1] = False


m = int(100000 ** 0.5)
for n in range(2,m+1) :
    if d[n] :
        for k in range(n,100001) :
            if n * k > 100000 :
                break
            d[n*k] = False
    if n * (n+1) > 100000 :
        break



dd = [0 for _ in range(b+1)]

for i in range(1,b+1) :
    if d[i] :
        dd[i] = 1
for i in range(2,b+1) :
    for j in range(2,b+1) :
        if i * j > b :
            break
        if d[j] :
            dd[i*j] = dd[i] + 1


answer_cnt = 0
for i in range(a,b+1) :
    if d[dd[i]] :
        answer_cnt +=1

print(answer_cnt )