[수학/소수] 백준 1418 K-세준수 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1418번: K-세준수

 

 

 

2. 문제 풀이

 N 이하 자연수 중에서 소인수의 최댓값이 K보다 작은 수들의 개수를 구하는 문제입니다.

 

N: 10, K: 3일 때, 10이하의 자연수 중 소인수가 3보다 작은 수들의 개수는 7입니다.

숫자	1	2	3	4	5	6	7	8	9	10
최대 소인수	x	2	3	2	5	3	7	2	3	5

 위 예제에서 5, 7, 10은 3보다 큰 소인수를 갖고 있습니다. 따라서 K-세준수는 7개입니다.

 

 

2022.02.08 - [Algorithm] - [Algorithm] 소수 판별 알고리즘, 에라토스 테네스의 체

[Algorithm] 소수 판별 알고리즘, 에라토스 테네스의 체

 먼저 K이상인 소수를 구하고 그의 배수들의 개수를 세면 됩니다. 소수 판별을 위해 에라토스 테네스의 체를 이용합니다. 이론적 설명과 구현 코드는 위 링크를 참조해주세요.

 

 

 

3. 코드

# 입력
N = int(input())
K = int(input())

# 에라토스 테네스의 체
primeList = [True] * (N+1)  # 최대 1부터 N까지 소수 판별
for i in range(2, int(N**0.5)+1):
    if primeList[i]:  # i가 소수라면
        for j in range(2 * i, N+1, i):  # 2i부터 100까지 i의 배수들은 False
            primeList[j] = False

 에라토스 테네스의 체로, 1부터 N까지의 소수를 판별합니다.

 

# N보다 작으면서 K이상인 소수의 배수들은 K-세준수가 아님
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)

 판별한 소수 중에서, K보다 큰 소수의 배수만 K-세준수가 아닙니다. K보다 큰 소수의 배수만 0으로 갱신합니다.

 이후 k_number의 개수를 출력합니다. sum(k_number)-1에서 -1은 0이 1로 되어있는 걸 빼준 것입니다.