7-1. 소수 구하기

소수(prime number)

• 자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수
• 즉, 1과 자기 자신 외에 약수가 존재하지 않는 수

소수 구하기의 핵심 이론

• 일반적으로 소수를 찾을 때는 2 이상부터 자기 자신보다 작은 수로 나눴을 때 나머지가 0이 아닌 수를 찾는 방식을 활용
  • 시간 복잡도가 커짐
• 대표적인 판별법으로 에라토스테네스의 체를 들 수 있음
  • 시간 복잡도는 일반적으로 $O(N\log(\log N))$ 정도임

원리

1. 구하고자 하는 소수의 범위만큼 1차원 리스트를 생성한다.

2. 2부터 시작하고 현재 숫자가 지워진 상태가 아닌 경우 현재 선택된 숫자의 배수에 해당하는 수를 리스트에서 끝까지 탐색하면서 지움

   • 이때 처음으로 선택된 숫자는 지우지 x

   • 주로 N의 제곱근까지 탐색

     

3. 리스트의 끝까지 2를 반복한 후 리스트에서 남아 있는 모든 수를 출력

7-2. 오일러 피

오일러 피 함수(P[N])

• 1부터 N까지 범위에서 N과 서로소인 자연수의 개수
• $\text{GCD}(n, k) = 1$을 만족하는 자연수 1 ≤ k ≤ n 의 개수

오일러 피의 핵심 이론

1. 구하고자 하는 오일러 피의 범위만큼 리스트를 자기 자신의 인덱스 값으로 초기화함