[Python | 백준 1418번] K-세준수

https://www.acmicpc.net/problem/1418

1418번: K-세준수

 

문제

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

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

입력

첫째 줄에 N, 둘째 줄에 K가 주어진다. N은 100,000보다 작거나 같은 자연수이고, K는 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 N보다 작거나 같은 K-세준수가 몇 개인지 출력한다.

 

---

내 풀이

# 31120kb 1388ms

# 10 3

# 1 2 3 4 5 6 7 8 9 10

# X 2 3 2 5 3 7 2 3 5 => 5,7,10 빼고 조건에 맞음

첫 번째 예제 문제를 직접 풀어보면 K-세준수는 K값만 넘지 않으면 포함된다.

이 때문에 1은 항상 K-세준수에 포함된다는 것을 알 수 있었다. (K=1이어도 1이 포함되므로)

 

N에 대해서 i=2부터 나눠주고 i 값을 1씩 더해주며 반복해서 나눠주기

이 때 나누는 값이 K를 넘으면 K-세준수에 해당하지 않으므로 0을 리턴,

다 나눠지면 K값보다 작은수로 나눠지므로  1을 리턴.

 

이런식으로 각 N에 대해서 K-세준수에 해당하는 수인지 0인지 1인지 구분하고 1일 경우 카운트해서 출력

num = int(input())
k = int(input())

def k_SejunNum(n):
    i = 2
    while i <= n:
      if i > k:
         return 0   # 나누는 소수가 k보다 크면 안됨

      if n % i == 0:
         n = n / i
      else:
         i = i + 1   # 그 외에는 계속 i를 1씩 증가

    return 1 # 정상적으로 모두 소수로 나눠졌다면 마지막 n은 1이 되면서 종료

cnt = 0
for N in range(2, num+1):
 if k_SejunNum(N):
  cnt += 1
print(cnt+1) # 모든 경우의 1은 K-세준수에 해당하므로 마지막에 따로 +1