글 읽기 - [파이썬] 문제가 자꾸 시간초과가 나옵니다

dyflajrwk 3년 전 0

제목이 곧 내용입니다 20프로에서 자꾸 시간초과가 뜨는데 어떻게 코드를 짜야 할까요?

import sys

T=int(sys.stdin.readline())
arr=[[] for j in range(T)]
for j in range(T):
    arr[j]=list(map(int,sys.stdin.readline().split()))

def checkAB(A,B):
    sum_an=0
    i=2
    while A>1:          ## 정수A가 완전히 소인수분해 될떄까지 코드 실행
        if A%i==0:      ## 정수A가 ai에 의해 나눠질 경우 ai를 sum_an에 더함
            A=A//i
            sum_an+=i
        else:       ## A가 더이상 해당 수로 나눠지지 않을 경우 나누는 인수값 올림
            i+=1
    if sum_an==B:   ## A의 모든 인수들의 합 sum_an이 B와 같은지 체크
        return 'yes'
    else:
        return 'no'

for j in range(T):
    print(checkAB(arr[j][0],arr[j][1]))

BaaaaaaaaaaarkingDog 3년 전 3

A가 굉장히 큰 소수일 경우(ex : 1000000009) 코드에 있는 소인수분해 방법은 O(A)이기 때문에 시간초과가 발생합니다.

한가지 팁을 드리자면 사실 소인수분해는 필요가 없습니다.

예를 들어

6 6

은 YES입니다.

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

문제

문제

출처

ICPC

[파이썬] 문제가 자꾸 시간초과가 나옵니다

dyflajrwk 3년 전 0

BaaaaaaaaaaarkingDog 3년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말