글 읽기 - [파이썬] 시간초과 질문

dyflajrwk 3년 전 0

소인수분해 하라고 해서 저런 방식으로 했는데 시간초과가 뜹니다. 어떤식으로 코드를 짜야 하나요?

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

def solution(N,K):
    i=2
    j=1
    while N>1:
        if N%i==0:  ##소인수 분해 중에 소인수값이 K보다 클 경우 거짓을 반환
            N=N//i
            j=i
            if j>K: return False
        else:
            i+=1
    return True     ##모든 루프를 돌아도 K보다 큰 소인수 값이 없었으므로 참을 반환

ans=0
for i in range(1,N+1):
    if solution(i,K): ans+=1    ##i가 K보다 작거나 같은 소인수값을 가질 때만 카운트

print(ans)

lem0nad3 3년 전 3

2부터 N까지의 수 중 하나를 X라고 해볼게요.

X가 Y(2<=Y<=K)로 나누어 떨어질때,

X를 Y로 나눌수 없을 때까지 계속 나눠주고, 2부터 K까지 이 작업을 반복한 후 X가 1이 됐다면,

이 수는 k보다 작은 소인수로만 이루어진 것이기 때문에, X는 "K-세준수"가 됩니다.

이렇게 하시면 Python3으로 1060ms, PyPy3으로는 280ms정도로 통과하실 수 있습니다.

dyflajrwk 3년 전 1

감사합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[파이썬] 시간초과 질문

dyflajrwk 3년 전 0

lem0nad3 3년 전 3

dyflajrwk 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말