Inflearn Community Q&A
asked
7. 소수(에라토스테네스 체) 시간초과 질문입니다.
Resolved
Written on
·
436
0
안녕하세요! 소수 강의를 듣고 질문이 있습니다.
강의에서 말씀해주신 것처럼 시간초과가 나서 Judge(Python-5).exe 파일로 실행시켜봤는데도 시간초과가 납니다. 제 코드에서 시간초과가 나는 이유가 어떻게 될까요??
n = int(input())
# 소수 = 1과 자기자신을 약수로 가지는 수
prime_number=[]
cnt=0
for i in range(2,n+1):
for j in range(1,i+1):
if i%j==0:
cnt+=1
if cnt == 2:
prime_number.append(i)
cnt=0
else:
cnt=0
print(len(prime_number))
python코테 준비 같이 해요!
Answer 1
1
codingcamp
Instructor
안녕하세요^^
j for 문이 1부터 i까지 1씩 증가하면서 j가 i의 약수인지 확인하는 방법은 시간초과나게 데이터를 만들었습니다.
영상에서 설명한 방법은 수학이론인 에라토스테네스체입니다. j for문이 i부터 시작해서 i의 배수로 반복하는 겁니다.