백준_1016_제곱ㄴㄴ수

문제

1016번: 제곱 ㄴㄴ 수

풀이

에라토스테네스의 체를 이용한 문제로, 위 코드에서는 1) 소수 구하기와  2) a, b사이의 값이 제곱수로 나누어지는지 확인하는 두 가지 기능이 한 번에 작성되어 있다. ans에 탐색해야하는 자연수의 개수를 담고, '제곱수의 배수'를 만날 때마다 1씩 값을 줄여나간다.

코드

def solution(a, b) :
    ans = b-a+1
    prime = [i for i in range(floor(b**0.5)+1)] # 소수를 저장할 공간
    number = [i for i in range(a, b+1)]   #a~b

    for i in range(2, len(prime)) :
        if prime[i]==0 : continue #소수가 아니면 넘어가기
        for j in range(i, len(prime), i) :
            prime[j] = 0 # 소수의 배수 지우기

        s_num = (i**2)*ceil(a/i**2) if i**2<a else i**2 # 가장 가까운 수 구하기
        for j in range(s_num, b+1, i**2) :
            if number[j-a]!=0 :
                number[j-a] = 0
                ans-=1
    return ans

from math import floor, ceil
a, b = map(int, input().split())
print(solution(a, b))

알고리즘 분류

• 수학
• 정수론
• 소수 판정
• 에라토스테네스의 체