백준 파이썬 1456 거의 소수

🚀접근하기

소수를 찾는 문제이므로, 아리스토테네스의 체를 이용하면 된다. 아리스토테네스의 체를 통해 찾은 소수를 바탕으로, 소수의 제곱부터 시작하여 'B' 이하의 모든 소수의 거듭제곱 값을 계산하여 이 값이 'A' 이상이면 해당 수를 "거의 소수"로 간주하면 된다. 

🎉코드

❗️메모리 초과 ❗️

A, B = map(int, input().split())
primes = [True] * (B + 1)
primes_set = []

for i in range(2, int(B ** 0.5) + 1):
    if primes[i]:
        primes_set.append(i)
        for j in range(i*i, len(primes), i):
            primes[j] = False
        

num = []
for i in primes_list:
    j = 2
    while i ** j <= B:
        if i ** j >= A:
            num.append(i ** j)  
        j += 1
            
print(len(num))

 

반복문의 범위를 (B**0.5)+1로 설정하는 이유는, 소수의 제곱이 B를 초과하지 않도록 하기 위해서다. 소수가 B의 제곱근보다 크면 소수^2는 B보다 커지므로, B의 제곱근까지만 소수를 확인해도 모든 "거의 소수"를 찾을 수 있다. 이 방식은 계산을 효율적으로 수행하고 필요한 소수들만 찾아내 메모리 사용을 최소화할 수 있다.

 

따라서 이와 같이 소수인 것들을 걸러서 primes_list에 넣어주고, 소수의 제곱부터 시작하여 B 이하의 모든 소수의 거듭제곱 값을 계산한다. 이 값이 A 이상이면 해당 수를 "거의 소수"로 간주하여 num 리스트에 넣어주면 된다.

 

근데.. 메모리 초과가 떴다.. 알고보니 초기 배열을 생성할 때에도, 소수의 거듭제곱으로 표현되는 "거의 소수"를 찾기 위해 B까지의 모든 소수를 알 필요가 없기 때문이다. "거의 소수"를 찾는 과정에서 중요한 것은 B의 제곱근까지의 소수이다. 따라서 primes = [True] * (int(B ** 0.5) + 1)로 바꿔주었다.

 

❗️맞았습니다❗️

A, B = map(int, input().split())
primes = [True] * int((B ** 0.5) + 1) 
primes_list = []

for i in range(2, int(B ** 0.5) + 1):
    if primes[i]:
        primes_list.append(i)
        for j in range(i*i, len(primes), i):
            primes[j] = False
        

num = []
for i in primes_list:
    j = 2
    while i ** j <= B:
        if i ** j >= A:
            num.append(i ** j)  
        j += 1
            
print(len(num))

성공!!!

💪다짐

골드 문제로 오니까 생각보다 메모리초과 문제, 시간초과 문제에 신경을 더욱 많이 써야한다는 것을 느꼈다.

모든 문제를 푸는데 있어서 가장 효율적이고 복잡성을 최소화하는 방법으로 풀 수 있도록 노력해야겠다!