글 읽기 - 파이썬 틀린 이유 - 반례 찾아주세요

T = int(input()) nums = list(map(int, input().split())) sosu = 0 # 소수 개수 출력 for i in nums: if i > 1: if i == 2 or i == 3: sosu += 1 elif i % 2 !=0 and i % 3 != 0: sosu += 1 print(sosu)

맞추신거 축하드립니다! 시간을 타이트하게 주는 문제에 도전하실때는 다음 내용을 참고하시면 좋을 것 같습니다.

소수 판별에서

for div in range(2,n):

나누어 떨어지는 지 확인

이렇게 짜면 O(n)의 시간 복잡도를 가지고 있습니다.

그런데 잘 생각해보면

어떠한 수가 나누어 떨어지면 그에 상응하는 나누어 떨어지는 수가 있습니다.

예를 들어 108이라고하면

1 2 3 4 ... 27 36 54 108

108 = 2* 54 = 3*36 ... 결국 sqrt(108)이 될때까지 나누어 떨어지는 수를 못 찾았다면 그 후에도 찾을 가능성은 전혀 없습니다.

따라서

div = 1

while div*div <= n:

나누어 떨어지는 지 확인

div+=1

로 짠다면 O(sqrt(n))만에 소수인지 아닌지 판별할 수 있습니다.

문제

문제

출처

ICPC

파이썬 틀린 이유 - 반례 찾아주세요

mhee4321 3년 전 0

dps2 3년 전 2

mhee4321 3년 전 0

dps2 3년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말