소수 판별 알고리즘의 정의 및 원리

이것이 코딩테스트다. 나동빈 신님의 강의를 바탕으로 작성하였습니다.

---

소수 판별 알고리즘.

  소수란 '1보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어떨어지지 않는 자연수'이다.
 - 6은 1, 2, 3, 6으로 나누어 떨어지므로 소수가 아님.
 - 7은 1과 7을 제외하고는 나누어 떨이지지 않으므로 소수이다.
 코테에서 어떤 자연수가 소수인지 아닌지 판별해야 하는 문제가 자주 출제되곤 함.

 (ㅡ) 해당 수에서 -1까지의 몸든 수를 확인하며 해당 수가 나누어 떨어진다면, 소수인지 아닌지. 판별가능
 

 

 2부터 x-1까지의 모든 자연수에 대하여 연산을 수행해야 한다.
  - 모든 수를 하나씩 확인한다는 점에서 시간 복잡도는 O(X)이다.
  > 10억이라면 2부터 10억까지의 수.
 

 

 '모든 약수가 가운데 약수를 기준으로 곱셉 연산에 대해 대칭을 이룸.
  예를 들어 16의 약수는 1, 2 ,4 8, 16 이다.
  이때 2 X 8 = 16 은 8 X 2 = 16 대칭이다.
 

 따라서 우리는 특정한 자연수의 모든 약수를 찾을 때 '가운데 약수(제곱근)까지만 확인'하면 된다.
  - 예를 들어 16이 2로 나누어떨어진다는 것은 8로도 나누어떨어진다는 것을 의미함.

 

 (1) 2부터 X의 제곱근까지의 모든 수를 확인하며 
   => for i in range(2, int(math.sqrt(x)) + 1): // 파이썬은 거듭 제곱 연산 제공함.
   => (C++) (int) sqrt(x); 으로 한다면 됨.
  => (java) Math.sqrt(x)
 (2) X가 해당 수로 나누어떨어진다면
 (3) 소수가 아님.
 (4) 나누어 떨어지지 않는다면 소수임.

 

 2부터 x의 제곱근(소수점 이하 무시)까지의 모든 자연수에 대해 연산을 수행해야 함.
  시간 복잡도는 O(N의 1/2 제곱)입니다.

 "다수의 소수 판별"
 '특정한 수의 범위 안에 존재하는 모든 소수'를 찾아야 할 땐?
 => "에라토스테네스의 체 알고리즘"사용할 수 있음.

 

 

 

---