[파이썬][프로그래머스] 소수 찾기

1. 문제

[level 1] 소수 찾기 - 12921

문제 링크

성능 요약

메모리: 17.1 MB, 시간: 240.79 ms

구분

코딩테스트 연습 > 연습문제

채점결과

정확성: 75.0
효율성: 25.0
합계: 100.0 / 100.0

문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

제한 조건

• n은 2이상 1000000이하의 자연수입니다.

입출력 예

n	result
10	4
5	3

입출력 예 설명

입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

2. 해결방법 시간복잡도

1. 에라토스테네스의 체 O(N^2)

3. 문제 해결 및 코드

---

• 주석을 참고하면서 이해를 돕습니다.

4. 알고리즘 및 해설

1. 파이썬에서 구현 가능한 가장 기초적인 반복문을 통한 소수 판별 알고리즘을 기반으로 만들었다.

    import math
    def primenumber(n):
        cnt = 0
        for i in range(2, int(math.sqrt(n) + 1)):
            if cnt >= 1:
                return False # 나누어 떨어지는 수가 존재할 경우
            if n % i == 0:
                cnt += 1
        if cnt == 0:
            return True # 나누어 떨어지는 수가 없을 경우
   

   • 제곱근을 통해서 접근하면 좀 더 빠르게 소수 판별이 가능하다.
     • 1과 자기 자신을 제외한 약수들은 모두 짝을 이루기 때문에 해당 방식으로 좀 더 빠르게 값을 찾을 수 있다.
     • 예시 : 10의 약수는 (1, 2, 5, 10)
     • 1과 10을 제외하면 2, 5 약수 2개는 서로 짝을 이루므로 제곱근으로 더 쉽게 풀이가 가능하다.
2. 여기서 사용한 방식은 소수 판별 알고리즘을 에라토스테네스의 체 방식으로 푼 방법이다.
3. n만큼 [True]로 가득찬 리스트를 만들어준다.
4. 이때 0과 1은 False로 바꿔준 이후 반복문을 통해 반복문이 돌아가는 위치값의 배수를 모두 False로 바꿔준다.
5. 이후 True(소수인 경우)를 카운트해서 출력한다.

5. 짚고 넘어가기

1. 소수 판별 알고리즘의 일종으로 에라토스테네스의 체를 사용하는 것이다.
   • 배열을 생성후 해당 배열의 위치값의 배수들을 빠르게 제거하여 소수를 대량으로 빠르게 판별할 수 있다.
2. 소수 여부 판별은 위의 단순 반복문을 통해서 판별이 가능하다.