[알고리즘] 백준 1418 파이썬 - K-세준수

 

1418번: K-세준수

문제

오세준은 어떤 자연수의 소인수중 최댓값이 K보다 크지 않을때 그 수를 K-세준수라고 부른다.

N보다 작거나 같은 자연수 중에 K-세준수가 총 몇 개인지 구하는 프로그램을 작성하시오.

 

문제풀이

n=int(input())
k=int(input())
#01
s = [0 for i in range(n+1)]
for i in range(2,n+1):
    if s[i] == 0:
        for j in range(i,n+1,i):
            if j%i == 0:
                s[j] = max(s[j],i)
#02
ans=0
for i in s:
    if i<=k:
        ans+=1
print(ans-1)

- #01 : 2부터 n까지 리스트 s에 소인수분해한 값 중 가장 큰 값을 저장한다.

- #02 : 만약 i가 k보다 작은 값이라면 ans에 1을 더한다.

           s는 처음 시작값이 0이기에 출력할 때 1을 빼고 ans를 출력한다.