글 읽기 - 파이썬 시간초과 ㅠ 고수님들도와주세요

odh3511 3년 전 0

에라토스테네스의 체를 이용한다고 해봤는데도 시간초과뜨네요...

어떻게 더 줄여야할까요

a,b= map(int,input().split())
x=[True]*(b+1)

for i in range(a,b+1):
    for j in range(2,i):
        if(i%j==0):
            for k in range(2*j,b+1,j):
                x[k]=False

for i in range(a,b+1):
    if(x[i] and i!=1):
        print(i)

djm03178 3년 전 0

코드의 로직을 생각해 봅시다.

i는 모든 수에 대해서 돌고 있고, j는 i를 나누어떨어지게 하는 수일 경우 모든 j의 배수 k에 대해서 x 배열에 체크를 해두고 있습니다.

그런데 j가 i를 나누어떨어지게 한다는 사실과 j의 배수들은 소수가 아니라는 사실이 어떠한 연관이 있나요? j가 나누어떨어지게 하는 i가 여럿 있을 때마다 j의 모든 배수에 대해서 체크하고 다시 체크하는 것을 반복해야 하는 걸까요?

odh3511 3년 전 0

감사합니다. 덕분에 깨달음을 얻었습니다! 소수인지 체크용으로 써봤던건데 이미 거기까지 도달한것으로 소수였습니다.

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

문제

문제

출처

ICPC

파이썬 시간초과 ㅠ 고수님들도와주세요

odh3511 3년 전 0

djm03178 3년 전 0

odh3511 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말