[Algorithm] 소수 구하기

😊백준_소수 구하기) https://www.acmicpc.net/problem/1929

😊프로그래머스_소수찾기)https://programmers.co.kr/learn/courses/30/lessons/42839

 

위와 같은 문제들을 풀며 소수 찾기 문제를 풀 때 원래 방식으로 풀면

시간 초과가 발생할 것이라는 생각이 들었다.

 

 

🙄 초기 코드)

for i in range(M,N+1): #소수찾기
        if i==2: #2는 소수
            arr.append(i)
        for j in range(2,i): 
            if i%j==0: #나눠지는 것이 있으면 소수가 아님
                break
            if j==i-1: #나눠지는 것이 없으면 소수
                arr.append(i)

- 이중 반복문을 사용하여 나눠지는 것이 있는지 없는지 판별한다.

여태 풀었던 문제에서 내가 사용했던 방식이다.  단계가 낮은 문제여서 시간 초과도 발생하지 않았었다.

이 방법으로는 한계..가 있다는 것을 알게 되었다.

 

 

🙄 새로운 코드)

 

사실, 새로운 방법이라고 할 것도 없다. 내가 늦게 이 방법을 이해(?) 적용(?)한 것 뿐...

'소수'라고 하면 다들 말하는 '에라토스테네스의 체'이다.

* 에라토스테네스의 체

= 소수를 찾는 방법이다.
- 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
- 2는 소수이므로 제외하고 2의 배수를 모두 지운다.
- 3도 소수이므로 제외하고 3의 배수를 모두 지운다.
- 위의 과정을 반복하면 구간의 모든 소수가 남는다.

 

위의 설명을 코드로 구현하면

    arr=[True]*(N+1)
    line=int((N+1)*0.5)
    for i in range(2,line+1):
        if arr[i]==True:
            for j in range(i+i,N+1,i):
                arr[j]=False

 

매번 미루다가 드디어 정리했다 🤗