[TIL-250221] 정수론 - 소수

어릴때 부터 수학을 포기했던 나는 프로그래밍을 배워서야 드디어 다시 수학에 입문하게 되었다.

알고리즘 공부를 하면서 가장 많이 쓰는 소수에대해 좀 작성해볼까 해서 작성한다.

 

소수란?

  - 1보다 큰 자연수중에서 1과 자신만을 약수로 가지는 수이다.

  예시) 소수: 2,3,5,7,11,13,17 ...

           소수가아닌수(합성수) : 4(2x2), 6(2x3) 8(2x4) ...

 

 주의 할 점 

   - 1은 자기 자신 하나 뿐이라서 소수가 아니다!

   - 2는 유일한 짝수 소수 이다. 

 

소수가 왜 중요할까? 

   - 정수론의 기초 단위다. 모든 자연수는 소수의 곱으로 표현할 수 있기 때문이다.

---

 

소수 판별 알고리즘

  1. 기본방법 (브루트포스)

    - 가능한 모든 경우를 전부 시도하는 방식이다.

    - 핵심 알고리즘 : 어떤 수 n이 주어졌을 때, 2부터 n-1까지 모든 수로 나눠보면서

                                나누어떨어지면 소수가 아니고 그렇지 않으면 소수라고 판별한다.

    - 단점 : 효율이 매우 낮고 시간복잡도 O(n)으로 커서 숫자가 커질 수록 느려진다.

 

   - 브루트포스 형식 :

     - 출력결과

 

---

소수판별 - 개선된 방법

   - 핵심  : 어떤 수  n이 소수가 아닌경우 반드시 n = axb 형태인데

    이때 둘 중 하나는 √n 이다 결론은 2부터 √n 까지 나눠보면 충분하다.

 

   - 브루트포스 개선된 방법 코드 예제

      = 출력값

 

 

    방법 3  에라토스테네스의 체

      알고리즘 

        1) 처음엔 모든수가 소수라고 가정한다. 

        2) 2부터시작해서 그 배수를 모두 지운다.

        3) 남아있는 수의 배수를 지운다.

        4) 반복하면 남은 수는 모두 소수 이다.

        = 에라토스테네스의 채 코드 예제

 

    = 출력결과

 

  - 총정리!

소수의 정의	1보다 크고, 약수가 1과 자기 자신뿐인 수
1은 소수가 아님	약수가 자기 자신 하나뿐
2는 유일한 짝수 소수	나머지 짝수는 2로 나누어짐
효율적인 소수 판별	제곱근까지만 검사
범위 내 소수 구하기	에라토스테네스의 체 알고리즘 사용

 

알고리즘 범위 시간 복잡도 설명

브루트포스	2~n-1	O(n)	비효율적이지만 단순함
제곱근까지 검사	2~√n	O(√n)	효율적이며 빠름
에라토스테네스의 체	2~n까지 모든 소수	O(n log log n)	많은 소수를 한 번에 구할 때 사용

 

---

오늘의 한줄 평 :  소수를 더해 합성수를 만들 수 있는 것에 대해 신기 하였고, 알고리즘 문제에 소수에 대해 많이 나와서 

                            작성하였다, 작성만 하는 것이 아니라 공부를 많이 해서 내것으로 만들었으면 좋겠다는 생각 입니다!