[Python] 소수 찾기 알고리즘

 

 파이썬으로  소수 찾기 알고리즘  

 

 

소수 찾기는 무언~가 어려운 느낌이 들어서 코딩테스트 연습할 때 항상 가장 마지막까지 남겨두곤 했다. 계속 이러면 더 못할테니 오늘 날잡고 아예 파헤쳐보자 !!! 👩‍💻

 

 

 

소수란 ? 

 

1과 자기 자신만으로 나누어 딱 떨어지는 1보다 큰 양의 정수 

 

ex) 2 -> 어떤 수로 2를 나누어 딱 떨어지는 수는 1,2 -> 2는 소수 

ex) 4 -> 어떤 수로 4로 나누어 딱 떨어지는 수는 (= 4를 나눌 수 있는 수)  1,2,4 => 1,4 본인 자신을 제외하고 2도 있기 때문에 4는 소수가 아님 

 

 

 

문제 : n 이 주어지고 1부터 n 까지의 소수의 개수를 구해보기

ex)  n=10이라면 소수는 = [2,3,5,7] 4개가 나온다 ! 

 

 

1. 완전 탐색 - 시간 복잡도 O(N) 

이중 for문으로 받은 n을 2부터 (1은 소수가 아님) n까지 for구문을 돌려 찾아보기 

def solution(n):
  answer=[]
  for i in range(2,n+1):
    count=0
    for j in range(2,i+1):
      if i%j==0: 
        count+=1
    if count==1:answer.append(i)
    
  print(answer)

solution(10)   # [2,3,5,7]

answer = 소수를 담을 리스트

1은 소수에 포함되지 않기 때문에 2부터 n까지 (n+1을 해야 n까지 i에 담을 수 있기때문) for 문을 돌리기 

그리고 이중 포문으로 2부터 i+1 까지 의 수를 for문 돌려서 i를 j로 나누어 나머지가 없을 경우 == 딱 맞아 떨어져 나눠지는 경우 count에 +=1 을 한다. 그리고 두 번째 for문이 끝났을 때 만약 if count가 1이라면 (나누어진 수가 본인 n 이라면, 1개) 해당 i를 answer에 담는다. 

 

 

 

2. 자기 자신의 절반까지 나누는 방법

 - 어차피 자기 자신의 절반 초과부터 자기 자신미만까지 본인을 나눌 수 있는 수가 없기 때문에 효율성에서 1번 코드보다 좋다. 

def solution(n):
  answer=[]
  for i in range(2,n+1):
    count=0
    for j in range(2, i//2+1):
      if i%j==0: 
        count+=1
    if count==0:answer.append(i)

  print(answer)

solution(10)   # [2,3,5,7]

2부터 n(본인) 까지 i에 for문을 돌려서 2부터 i//2 +1 본인을 반으로 나눈 수 +1 (까지 해야 나눈 수까지 담기기 떄문) 까지 j로 이중 for문을 돌린다. 딱 맞게 나눠진다면 count += 1을 한다. 자기 자신은 자기 자신으로 나눠지기 때문에 if count==0: 이라면 (2부터 자기 자신의 절반까지의 수 중, 자기 자신을 나눌 수 있는 수가 없다면 ) answer에 담아 출력 

 

 

 

 

3. 에라토스테네스의 체 

범위 내에서 합성수를 지우는 방식으로 소수를 찾는다. 

-> 제일 작은 소수 2부터 n-1까지의 수 중에서 2의 배수를 모두 지우고 남은 수들 중에서 3의 배수를 거르고 남은 수들 중에서 4의 배수를 거르고.........반복하다보면 제곱근N까지 나누어서 걸러지지 않고 남은 수들이 소수 ! 

def solution(n):
  a=[False,False,]+[True]*(n-1)     # [False, False, True, True, True, ... ] 배열 0과 1은 이미 소수가 아니므로 False
  primes=[]     # 소수를 담을 공간 

  for i in range(2, n+1):   # i = 2~ n까지 
    if a[i]:    # 만약 a 리스트의 i index의 요소가 True 일 경우 
      primes.append(i)   # i를 primes 리스트에 담기 (i는 소수) 
      for j in range(2*i,n+1,i):  # i를 이미 담았기때문에 for문을 2*i부터 시작 (i의 배수) 
        a[j] = False   # i가 2인 경우 10 안의 2로 나눠지는 모든 수를 False로 바꾸기 
  print(primes)

solution(10) # [2,3,5,7]

위의 코드를 설명해보면 처음 0부터 n까지의 리스트 a를 만든다. 이 때 리스트는 0이 존재해서 False를 넣어주었기 때문에 [True]*(n-1)을 해서 길이를 0~n까지로 맞춰준다. (개수는 n+1이 됨) 

 

2부터 n 까지 i에 담아 for문을 돌린다. 만약 a리스트의 i인덱스가 True라면 소수이므로 primes에 넣는다. -> 소수인걸 아는 이유는 2~n까지의 수 중 2는 일단 소수이므로 담고, 3도 소수, 4는 이미 2를 담아 이중 for문에서 False로 만들었기 때문. 

 

그리고 해당 수의 2배 수부터 n+1 까지 이중 for문을 돌려 해당 i의 배수들을 모두 False로 만들어 준다. (이 후에 해당 수들을 다시 연산할 필요가 없도록) 

 

 

 

 

 

4. 에라토스테네스의 체 set 버전 

에라토스테네스의 체 방법을 set() 을 사용하여 - 빼기로 푸는 방법 

* set()은 중복허용이 되지않고, 더하기, 빼기가 가능한 { } 신기한 매서드 

def solution(n):
    num=set(range(2,n+1))  # 2부터 n까지 set으로 {2,3,4,5,6,~} 만들기 

    for i in range(2, n+1):
      if i in num:   # 만약 i 가 num 안에 있다면 
        num-=set(range(2*i, n+1, i))   #num에 set(range(2*i, n+1, i))를 뺀 값을 다시 담기 반복 

    print(num)
                
solution(10)

위의 방법은 3번의 에라토스테네스의 체 기존 방법을 set() 매서드를 이용하여 더 간단하게 구현했다. 두 번째 이중 for문에서 만약 i가 num 변수 안에 있다면 num 에 i*2 (i값의 두배 부터 ~ n+1까지 i 씩 + 한 ) 값의 set을 빼서 담았다. 3번 방법은 리스트를 만들어 해당 요소를 True로 바꾸어주었다면 위의 방법은 리스트 없이 바로 빼기 ! 

 

ex) i=2일 때 set(2*i, n+1,i)는 = { 4,6,8,10} 을 {2,3,4,5,6,7,8,9,10} 에서 제외 => {2,3,5,7,9}

    i =3일 때 set(2*i, n+1, i)는 = {6,9} 제외 => {2,3,5,7}

 

 

---

 

 

 

소수를 찾는 방법은 아직 100% 알 수 없다고 한다. 소수를 두 번 더하면 더이상 소수가 아니게 되고... 뭔가 소수도 무한대일 것 같은 생각이 든다. 소수를 찾는 더 좋은 알고리즘이 있다면 이어서 더 포스팅을 해봐야겠다 !