맞았던 답안 공개

# 범위를 루트값 까지만 비교
# 예를 들어 12를 판별할때 2부터 루트12까지 비교 

import sys

a,b = map(int, sys.stdin.readline().split())
arr=[]
x=0

for i in range(a,b+1):
    temp=True
    if i==1: continue
    for j in range(2,int(i**0.5)+1): #11
        if(i%j==0):
            temp=False
            break

    if temp: 
        arr.append(i)
        print(arr[x])
        x+=1

자꾸 시간초과가 나서 다른 사람들의 코드를 참고했기에 오로지 내가 풀었다고 할 수 없다. 그리고 수학 안한지 너무 오래되서 1이 소수가 아니라는 사실을 알게되었다...

처음 제출했던 답안

a,b = map(int, input().split())
arr=[]

for i in range(a,b+1):
    temp=0
    for j in range(2,i): #11
        if(i%j==0):
            temp+=1

    if(temp==0): arr.append(i)

for i in range(len(arr)):
    print(arr[i])

여기서 '시간 초과' 에러를 처음 만났다.
그래서 input()을 sys.stdin.readline()으로 바꿔보기도 하고 for문을 줄이려고 arr를 프린트하는 부분을 위에 for문에 합쳐주었다. 그런데도 계속 에러가 났다.

에라토스테네스의 체

그러다 검색하다 발견한게 에라토스테네스의 체 이다.
소수 판별 알고리즘의 속도를 높이는 가장 대표적인 방법이다.
판별하고자 하는 수의 제곱근까지만을 검증해 소수인지 판별하여, 대량의 소수를 한번에 판별할 때 속도가 빨라 유용하다고 한다.

예를 들어, 13이 소수인지 아닌지 판별하고싶을때
처음에 나는 12를 2부터 12까지 나누었을때 나머지가 0이 아닌것을 소수라고 생각하여 알고리즘을 짰다.

그런데 에라토스테네스의 체를 적용하면
13을 2부터 12까지가 아닌, 2부터 루트12(2루트3=3.xx)까지만 본다. 왜 그럴까?

출처: https://imdona.tistory.com/25

이 사람이 그린 예제사진을 보면 이해가 한번에 된다.
애초에 12까지 나눌 필요 없이 3까지만 나누어도 소수판별이 가능하다!

배운것

1. 1은 소수가 아니다.
2. 소수를 판별할때 판별할 수 i 의 i-1 까지 다 나눠볼 필요 없이 루트 i 까지만 나눠봐도 판별가능하다.
3. continue를 쓰면 처음으로 돌아간다.