K-세준수

1418번: K-세준수

 

나의 풀이

import sys

# 소수 check
def _sosu_check(num):
    if (num == 1):
        return False
    for i in range(2, int(num**(1/2))+ 1):
        if (num % i == 0):
            return False
    return True

# max value return
def _max_value_return(now_n):
    answer = 0
    for i in range(1, int(now_n**(1/2)) + 1):
        if (now_n % i == 0):
            if _sosu_check(i):
                answer = max(answer, i)
            if (i**2 != now_n):
                if _sosu_check(now_n // i):
                    answer = max(answer, now_n // i)
    return answer

# 최종 k 준수 return
def _k_score(N, K):
    answer = 0
    for i in range(1, N + 1):
        if (_max_value_return(i) <= K):
            answer += 1    
    return answer

N = int(sys.stdin.readline())
K = int(sys.stdin.readline())
print(_k_score(N, K))

 

시간 복잡도

for i in range(1, N + 1) : N 까지 순회하며 세준수 확인 ( 선형 시간 복잡도 )
    _max_value_return : 세준수 최댓값을 찾는 함수 ( 로그 시간 복잡도 )
        _sosu_check : 소수 체크 함수 ( 로그 시간 복잡도 )
해당 알고리즘 시간 복잡도 : 선형 * 로그 * 로그 시간 복잡도 ( O(n log(log n) )