<p>안녕하세요! 소수 강의를 듣고 질문이 있습니다.</p>
<p>강의에서 말씀해주신 것처럼 시간초과가 나서 Judge(Python-5).exe 파일로 실행시켜봤는데도 시간초과가 납니다. 제 코드에서 시간초과가 나는 이유가 어떻게 될까요??</p>
<p></p>
<p><img src="https://cdn.inflearn.com/public/files/posts/2968c46f-f975-44e6-a57e-eea240275ac4/blob" alt="" /></p>
<p></p>
<div style="color: #d4d4d4; background-color: #1e1e1e; font-family: Consolas, 'Courier New', monospace; font-size: 14px; line-height: 19px; white-space: pre;">
<div>n&nbsp;=&nbsp;<span style="color: #4ec9b0;">int</span>(<span style="color: #dcdcaa;">input</span>())</div>
<div><span style="color: #6a9955;">#&nbsp;소수&nbsp;=&nbsp;1과&nbsp;자기자신을&nbsp;약수로&nbsp;가지는&nbsp;수</span></div>
<div>prime_number=[]</div>
<div>cnt=<span style="color: #b5cea8;">0</span></div>
<div><span style="color: #c586c0;">for</span>&nbsp;i&nbsp;<span style="color: #c586c0;">in</span>&nbsp;<span style="color: #dcdcaa;">range</span>(<span style="color: #b5cea8;">2</span>,n+<span style="color: #b5cea8;">1</span>):</div>
<div>&nbsp;&nbsp;&nbsp;&nbsp;<span style="color: #c586c0;">for</span>&nbsp;j&nbsp;<span style="color: #c586c0;">in</span>&nbsp;<span style="color: #dcdcaa;">range</span>(<span style="color: #b5cea8;">1</span>,i+<span style="color: #b5cea8;">1</span>):</div>
<div>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color: #c586c0;">if</span>&nbsp;i%j==<span style="color: #b5cea8;">0</span>:</div>
<div>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cnt+=<span style="color: #b5cea8;">1</span></div>
<div>&nbsp;&nbsp;&nbsp;&nbsp;<span style="color: #c586c0;">if</span>&nbsp;cnt&nbsp;==&nbsp;<span style="color: #b5cea8;">2</span>:</div>
<div>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;prime_number.append(i)</div>
<div>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cnt=<span style="color: #b5cea8;">0</span></div>
<div>&nbsp;&nbsp;&nbsp;&nbsp;<span style="color: #c586c0;">else</span>:</div>
<div>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cnt=<span style="color: #b5cea8;">0</span></div>
<div></div>
<div><span style="color: #dcdcaa;">print</span>(<span style="color: #dcdcaa;">len</span>(prime_number))</div>
</div>

<p>안녕하세요^^</p>
<p>j for 문이 1부터 i까지 1씩 증가하면서&nbsp; j가 i의 약수인지 확인하는 방법은 시간초과나게 데이터를 만들었습니다.</p>
<p>&nbsp;영상에서 설명한 방법은 수학이론인 에라토스테네스체입니다. j for문이 <strong>i부터 시작해서 i의 배수</strong>로 반복하는 겁니다.</p>

인프런 커뮤니티 질문&답변

7. 소수(에라토스테네스 체) 시간초과 질문입니다.