[샛길공부] 소수판별,에라토스테네스의 체(feat. 이코테 유튜브강의)

 

백준 문제를 풀다가 우후죽순으로 계속 생겨나는 모르는 단어들

갑자기 공부하게 만든 문제 풀기는 아래 참고 👇👇👇

https://coding-nurse.tistory.com/43

---

* 강의 채널 : 동빈나

* 강의 이름 : (이코테 2021 강의 몰아보기) 9. 코딩테스트에서 자주출제되는 기타 알고리즘

* 강의 링크 : https://youtu.be/cswJ1h-How0

 

 🎠 소수 판별 알고리즘

   * 소수란? : 1과 나 자신을 제외한 자연수로 나누어 떠어지지 않는 자연수 

 

 [기본] 소수 판별 알고리즘 

 ▶ 단점: 시간이 엄청 오래 걸림. x 값이 커질수록 하나하나 확인해야 할 값이 많아져버림

#소수 판별 알고리즘
 
def sosu(x):
    for i in range(2,x):    #1과 자기자신 제외
        
        #조건: i로 나누면 나누어떨어짐
        if x % i == 0:   
            return '소수 X'
   
    return '소수 O'
 
print(sosu(4))    #소수 X 출력
print(sosu(7))    #소수 O 출력

 

 

 [업그레이드] 소수 판별 알고리즘 

약수의 성질을 이용해서 업그레이드 할 수 있다.

▶ 단점: 조금 나아졌지만 그래도 x값이 크면 시간이 오래 걸림.

장점은 메모리 차지 에라토스테네스의 채보다 적게 차지하는 것?

 

약수의 성질 : 모든 약수가 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이룸

- ex) 16의 약수는 1 2 4 8 16 임  ------> 2*8 = 8*2 대칭

- 따라서, 특정한 자연수의 모든 약수를 찾을 때 가운데 약수(제곱근)까지만 확인하면 된다. 

#업그레이드 소수 판별 알고리즘-----------------
 
import math
 
def sosu_upgrade(x):
   #제곱근을 int해서 버림되었으니, 1을 더해줌
    for i in range(2, int(math.sqrt(x))+1):
        
        #조건: i로 나누면 나누어떨어짐
        if x % i == 0:   
            return '소수 X'
        
    return '소수 O'

---

 🎠 에라토스테네스의 체

 * 에라토스테네스의 체란? 다수의 자연수에 대하여 소수를 판별할 때 사용됩니다. (즉, 특정한 수의 범위 안에 존재하는 모든 소수를 찾아야 할 때)

▶ 단점: 속도는 엄청 빠르지만, 메모리를 많이 차지함

동작 과정  
1) 2부터 N까지의 모든 자연수를 나열한다.
2) 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.
3) 남은 수 중에서 i의 배수를 모두 제거한다 (i는 제거하지 않는다!)
4) 더 이상 반복 할 수 없을 떄까지 2번과 3번의 과정을 반복한다.

#에라토스테네스의 체
 
import math
 
n= int(input()) 
 
#처음엔 모두 소수(True)라고 리스트 만들기
#소수가 아니라면 False로 제거처리
array=[True for _ in range(n+1)]
 
# 2부터 제곱근까지 모든 수 확인하기
for i in range(2,int(math.sqrt(n)+1)):
    
    #조건: 리스트안 남은 수가 소수인 경우
    if array[i] == True:
        
        j=2 #자신은 포함시키면 안되니까 2부터 시작 
        while i*j <=n: #i의 배수를 제거처리
            array[i*j] = False
            j+=1
                        
#array 반복 돌면서 살아남은 소수(True) 조회
for k in range(2, n+1):
    if array[k]: 
        print(k, end=" ")
 

---

🧐공부 한줄 평 : 소수 알고리즘마다 각 장단점이 있으니, 잘 골라서 사용하자