[백준 / Python] #1124 언더프라임

문제

 

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

1124번: 언더프라임

---

Algorithm

자연수 X를 소인수분해를 하면 소수들의 곱이 되고, 소인수의 개수가 소수이면 자연수 X가 언더프라임이다. 범위를 입력받아 범위안에 있는 언더프라임의 개수를 찾는 문제이다. 

a와 b 사이가 최대 100000이고, 소인수분해하는데 루트100000정도 쓴다고 하면 31,622,776정도 나오므로 시간제한에 돌 수 있다고 생각해서 아래처럼 코드를 구성했다.

자연수의 범위 a,b를 입력받는다 -> a를 소인수분해하고 소인수분해한 소수들의 개수를 구하고 소수인지 판별한다. -> a+1을 소인수분해하고 소인수분해한 소수들의 개수를 구하고 소수인지 판별한다. -> ... -> b를 소인수분해하고 소인수분해한 소수들의 개수를 구하고 소수인지 판별한다. 의 순서가 될것이고, 소인수분해와 소수판별을 구현해주면 된다고 생각했다.

소인수분해를 하고 소인수의 개수를 return해줄 함수 find를 정의한다.

find가 리턴해준 값이 소수인지 판별하기 위해 에라토스테네스의 체를 이용하여 is_prime 배열을 만든다. is_prime배열은 b까지 만들면 되고,  is_prime 배열의 값이 True면 값에 더해주고, 아니면 continue한다.

마지막으로 개수를 출력해주면 된다. 

---

 

 

Code

input = __import__('sys').stdin.readline
import math

def find(n):
    cnt=0
    for i in range(2, int(math.sqrt(n) + 1)):
        while n % i == 0:
            cnt+=1
            n //= i
    if n != 1:
        cnt+=1
    return cnt


a,b = map(int,input().split())
is_prime = [True for i in range(b + 1)]

is_prime[1] = False
for i in range(2, b + 1):
    if not is_prime[i]:
        continue
    
    for j in range(i * i, b + 1, i):
        is_prime[j] = False
cnt=0
for i in range(a,b+1):
    if is_prime[find(i)] == True:
        cnt+=1
print(cnt)