[백준/파이썬] 1418번 K-세준수 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 1418번 K-세준수
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

1부터 N까지의 수 중에서 가장 큰 소인수가 K 이하인 수(K-세준수)의 개수를 구하는 문제입니다.

코드

n, k = int(input()), int(input())

c = 1
for i in range(2, n+1):
    l = []
    j, tmp = 2, i
    while j*j <= tmp:
        if tmp % j == 0:
            tmp //= j
            l+=[j]
        else: j+= 1
    l.append(tmp)
    if max(l) <= k: c+= 1
print(c)

설명

각 수 i를 소인수분해해 소인수 목록을 만들고, 그중 최댓값이 K 이하인지 검사합니다.

조건을 만족하면 카운트하고, 최종 개수를 출력합니다.

---

• 백준 문제풀이 전체 목록 보기

---