[Algorithm/Python] 파이썬 소수 찾기(Python Program to Check Prime Number using Sieve of Eratosthenes)

문제

1개 이상의 자연수가 들어있는 배열이 주어졌을 때, 소수의 개수 출력하기

 

풀이

완전탐색 이용하기

def getPrimeNum(n):
    if n == 1 :
        return False
    elif n == 2 :
        return True
    for i in range(2, n):
        if n % i == 0 :
            return False
    return True

answer = 0
# arr 가 주어진 배열
for k in arr :
    if getPrimeNum(k) :
        answer += 1
        
print(answer)
        

• for 문을 이용해 배열의 원소를 차례대로 호출한다.
• 소수의 정의는 1과 그수 자신 이외의 자연수로는 나눌 수 없는, 1보다 큰 자연수(출처:위키백과) 이기 때문에 for 문을 통해 2부터 n-1까지 n을 나눠서 나누어 떨어진다면 그 수는 소수가 아니기 때문에 False를 리턴한다.
• True 인 개수만 세서 출력하면 된다.

에라토스테네스의 체 방법으로 구현하기

def getPrime(n):
    primes = [True] * n
    m = int(n ** 0.5)
    for i in range(2, m+1):
        if primes[i] == True:
            for j in range(i+i, n, i):
                primes[j] = False
    return [i for i in range(2,n) if primes[i] == True]

# arr가 주어진 배열
primeList = getPrime(max(arr)+1)

answer = 0
for k in arr :
    if k in primeList:
        answer += 1
print(answer)

• 에라토스테네스의 체를 이용한 풀이이다.

ex) n = 10

• 에라토스테네스의 체 방법이란?
  • 내가 원하는 구간안에 있는 모든 수를 나열한다.
  • 자기 자신을 제외한 2의 배수를 지운다.
  • 자기 자신을 제외한 3의 배수를 지운다.
  • 자기 자신을 제외한 4의 배수를 지운다 -> 2의 배수에서 다 지워졌기 때문에 안 해도 된다.
  • 자기 자신을 제외한 5의 배수를 지운다.
  • 위를 반복하면 소수만 남는다.
• 이 방법을 코드로 구현해본다면?
  • 먼저 모든 구간의 수를 소수라고 판단해둔다 -> True로 설정
  • 이 구간은 0부터 시작되어서 n-1 까지 진행되기 때문에 애초에 getPrime 함수를 부를 때 원하는 구간 +1을 해서 소환했다.
    • 이 이유는 인덱스 값이 숫자가 되기 위함이다 ! (ex. [2] -> 숫자 2가 소수인가 아닌가)
  • for 문의 구간은 n의 제곱근까지 진행한다.
  • 자기 자신은 제외하기 때문에 i+i 를 시작으로 잡고 계속 그 수의 배수만큼 늘려주면서 False 값으로 바꿔준다.
  • 이제 True 인 값은 소수이기 때문에 소수인 인덱스 값만 배열에 저장해서 return 해준다.

 

관련 문제

코딩테스트 연습 - 소수 찾기

1978번: 소수 찾기

---

 

숫자가 작고 하나의 숫자를 받아 소수를 판별한다면 1번 방법이 더 빠를 거 같고

그게 아니면 2번이 더 효율성이 있을 거 같다!

@미닛메이드 Minnit