알고리즘 - Python / 백준 - 1418번 : K-세준수

1418번: K-세준수 (acmicpc.net)

1418번: K-세준수

 

---

풀이

• 어떤 자연수의 소인수중 최댓값이 K보다 크지 않을 때 그 수를 K-세준수 라고 하고 범위 내의 K-세준수가 몇 개인지 찾는 문제다.
• 에라토스테네스의 체를 활용해 각 수의 소인수중 최댓값을 배열에 저장하고 이후 배열을 돌며 조건을 만족하는지 확인하는 방법으로 문제를 해결하였다.

 

import sys
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())

s = [0 for i in range(n+1)]
for i in range(2,n+1):
    if s[i] == 0:
        for t in range(i,n+1,i):
            if t%i == 0:
                s[t] = max(s[t],i)
ans = 0
for i in s:
    if i <= m:
        ans += 1
print(ans-1)

---