[BOJ/백준] 1418 - K-세준수 (Python)

문제

문제링크

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

N보다 작거나 같은 자연수 중에 K-세준수가 총 몇 개인가.

 

풀이

에라토스테네스의 체를 사용해서 풀었다. 2부터 시작해 배수들을 지우면 남은 수는 모두 소수가 된다.

어떤 소수 i가 j를 나눌 수 있으면 j의 소인수는 i이다.

저장용 배열 primes에서 중첩 for문을 사용해 해당 index의 최대소인수가 저장된다.

아래 코드를 보면 여러개의 소인수가 존재할 경우 가장 큰 소인수가 배열에 저장되는 것을 알 수 있다.

 1일 경우는 따로 처리해야 하므로, 1이고 K가 1보다 같거나 클 경우 cnt를 증가시킨다.

저장용 배열을 확인하면서 K보다 작거나 같은 경우에만 cnt를 증가시킨다.

 

코드

N=int(input())
K=int(input())

primes = [0] * (N + 1)
for i in range(2, N+1):
  if primes[i]==0:
    for j in range(i, N+1, i):
      primes[j]=i

cnt=0
for i in range(1, N+1):
  if i==1 and i<=K: cnt+=1
  elif primes[i]<=K:cnt+=1
print(cnt)