BOJ 1418 - K-세준수

문제

1부터 N까지의 수 중 K보다 큰 소인수를 가지지 않는 수(K-세준수)의 개수를 구하라.

입력

첫째 줄에 N, 둘째 줄에 K가 주어진다.

출력

K-세준수의 개수를 출력한다.

예제

입력	출력
`10` `2`	`4`

풀이

에라토스테네스의 체로 소수를 구한 뒤, K보다 큰 소수의 배수를 모두 제거하면 남는 수가 K-세준수이다.

에라토스테네스의 체로 N 이하의 소수를 모두 구한다
k_number 배열을 모두 1로 초기화한다
K보다 큰 소수 각각에 대해, 그 배수를 모두 0으로 표시한다
k_number 배열의 합에서 1(인덱스 0)을 빼면 답이다

핵심 아이디어: K 이하의 소수만으로 이루어진 수를 직접 구하는 대신, K 초과 소수의 배수를 제거하는 역발상으로 효율적으로 해결한다.

코드

N = int(input())
K = int(input())
 
primeList = [True] * (N + 1)
for i in range(2, int(N**0.5) + 1):
    if primeList[i]:
        for j in range(2 * i, N + 1, i):
            primeList[j] = False
k_number = [1] * (N + 1)
 
for i in range(2, N + 1):
    if primeList[i] and i > K:
        for j in range(i, N + 1, i):
            k_number[j] = 0
 
print(sum(k_number) - 1)

복잡도

시간: O(N log log N)
공간: O(N)

문제