글 읽기 - 시간초과 질문드립니다 [파이썬]

coding_master 2년 전 0

무엇때문에 시간초과가 일어나는지 모르겠습니다 ㅠㅠ

import sys
a,b = map(int,input().split())
for i in range(a,b+1):
    num = 0
    for ii in range(1,int(i)+1):
        if int(i) % ii == 0:
            num += 1
    if num == 2 :
        num = 0
        print(i)

circlezer0 2년 전 0

위의 코드는 한 수 N을 판정하기 위해서 N번의 연산을 수행해야 합니다.

1부터 N까지의 소수를 구한다 했을 때 O(N^2), N<=1000000이므로 너무 많은 연산이 수행됩니다.

에라토스테네스의 체에 대해서 공부해 보시는걸 추천드립니다.

coding_master 2년 전 0

넵,감사합니다 ^^

coding_master 2년 전 0

넵 감사합니다 ^^

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

문제

문제

출처

ICPC

시간초과 질문드립니다 [파이썬]

coding_master 2년 전 0

circlezer0 2년 전 0

coding_master 2년 전 0

coding_master 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말