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

📝 문제

💡 오세준은 어떤 자연수의 소인수중 최댓값이 K보다 크지 않을때 그 수를 K-세준수라고 부른다.
N보다 작거나 같은 자연수 중에 K-세준수가 총 몇 개인지 구하는 프로그램을 작성하시오.

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

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

 

문제링크

1418번: K-세준수

---

✅ 풀이

import math
def sosu(num):
    for i in range(2, int(math.sqrt(num)) + 1):
        if num % i == 0:
            return False
            break
    else:
        return True

def soinsu(num):
    li = []
    for i in range(2,int(math.sqrt(num))+1):
        if num % i == 0:
            if sosu(i):
                li.append(i)
            if sosu(num//i):
                li.append(num//i)

    if len(li) == 0:
        li.append(num)
    return li

def sejunsu(num):
    if max(soinsu(num)) <= k:
        return True
    else:
        return False

n = int(input())
k = int(input())
cnt = 0

for i in range(1, n+1):
    if sejunsu(i):
        cnt += 1

print(cnt)

💡 문제의 테스트 케이스에서 10, 3이 입력으로 주어졌을 때
왜 출력으로 7이 나오나 엄청 고민을 했었는데..
그냥 문제에서 1을 소수로 취급하는 오류 때문이었다.. (고쳐주세요)

sosu, soinsu 함수를 통해 n 이하의 숫자들에 대해 각각 그들의 소인수를 구하고,
소인수들 중 가장 큰 수가 k 이하인지를 판별하여 카운팅 해주었다.