1과 자기 자신으로만 나누어 떨어지는 수를 말한다. 즉 3은 소수다. 3은 3으로만 나누어 떨어지기 때문이다. 4는 소수가 아닌데, 이유는 4가 아닌 2로도 나누어 떨어지기 때문이다. 그런 면에서 생각해보면 2를 제외한 모든 짝수는 소수가 아니다.

참고로 발음이 [소쑤]가 된다고 한다.

소수의 계산

100까지의 소수를 구한다고 가정해 보자.

2는 소수이면서 짝수이므로 특성이 약간 다르니까 2는 포함해서 시작한다고 치고, 3부터 100까지의 수 중에 소수를 구하는 방법을 생각해 보면 다음과 같을 것이다.

  1. 3~100 사이의 숫자 n을 선택한다.
  2. 3~(n-1)까지의 숫자를 n에 나누어 본다. 즉, n/3, n/4, …, n/(n-1)을 시도한다.
  3. 나누어 떨어지는 케이스가 발생시 n은 소수가 아니다.
  4. 나누어 떨어지는 케이스가 없으면 n은 소수이다.

여기서 n-1을 생각해 보자. 나눗셈은 뺄셈을 반복하는 것이므로, n=2인 경우를 제외하고는 n을 n-1로 나누면 당연히 나누어 떨어지지 않는다. n을 나눌 수 있는 가장 큰 숫자는 n/2가 되므로 n-1을 n/2로 변경하자.

또 생각해보면 짝수인 경우는 무조건 2의 배수가 되므로 이것 또한 홀수만 선택하도록 바꿀 수 있다. 이제 이 내용으로 다시 방법을 써 보면 다음과 같다.

  1. 3~100사이의 홀수 n을 선택한다.
  2. 3~(n/2)까지의 숫자를 n에 나누어 본다. 즉, n/3, n/4, …, n/(n/2)을 시도한다.
  3. 나누어 떨어지는 케이스가 발생시 n은 소수가 아니다.
  4. 나누어 떨어지는 케이스가 없으면 n은 소수이다.

소수의 반대 개념인 합성수를 생각해 보자. 소수가 아닌 것들은 합성수라고 부르는데, 이름이 왜 합성수냐 하면 소수의 곱으로 만들어지는 수이기 때문이다. 6은 소수 2와 소수 3의 곱이므로 소수가 아니고 합성수가 된다.

어떤 수 m을 어떤 수 n으로 나눌 수 있다는 것에 대해 생각해 보자. m은 ab의 곱으로 이루어졌고 n은 b로 이루어진 수라고 생각했을 때 이 두 수는 나누어지는가? 라고 생각하면 나누는 것이 가능하다.

m/n == ab/b == a, m/n == a

마찬가지로 소수 m이 p와 q, 그리고 r로 이루어진 수일때, 어떤 수 n으로 나누는 것이 가능하려면 n이 p,q,r의 조합으로 이루어진 합성수여야만 한다. 예를 들어 pqr을 나누기 위해서는 1, p, q, r, pq, rq, pr, 그리고 pqr 총 8개의 합성수만이 가능하다. 예를 들어 p=2, q=3, r=5일 경우 다음이 성립할 것이다.

  • pqr = 30
  • 1과 p, q, 그리고 r의 조합으로 만드는 합성수: [1,2,3,5,6,10,15,30]

우리는 이 합성수를 약수(divisor)라고도 부른다. 어쨌든 이걸로 알 수 있는 사실은 다음과 같다.

어떤 수 m이 소수인지 확인하기 위해서는 0 < n < m인 모든 소수 n으로만 나누어봐도 된다.

m이 소수라면 합성수는 1*m으로만 나오는 것이 가능하므로 m은 n으로 나누어지지 않는다. 마찬가지로 m이 소수가 아니라면 소수들의 곱으로 이루어진 합성수이므로, m을 이루는 특정 소수로 나누는 것이 가능하다.

따라서 절차는 또 이렇게 바뀐다.

  1. 소수 리스트 l을 생성하고 여기에 2를 추가한다.
  2. 3~100사이의 홀수 n을 선택한다.
  3. n을 소수 리스트 l의 모든 소수 m으로 나누어 본다. 물론 m은 n/2의 조건을 가진다.
  4. 나누어 떨어지지 않는다면 소수 리스트에 n을 추가한다.
  5. 나누어 떨어진다면 다른 홀수 n을 선택하고 다시 진행한다.

어떤 수 n의 소수 판정을 위해 나눗셈을 하는 경우에 대해 다시 한 번 생각해 보자. n이 소수인지 아닌지를 판별하기 위해서 우리는 3~(n-1)의 수를 나눠보는 것으로 처음에 생각했다가, 3~(n/2)의 경우에 대해서 나누는 것으로 최적화했다. 40이란 숫자를 나눌 수 있는 최대한의 수는 40/2, 즉 20이 되기 때문이다.

어떤 수 a가 있고 이의 제곱근 b를 생각해 보자. 아래처럼 써볼 수가 있다.

sqrt(x) = a

이는 a2가 x와 같음을 뜻한다.

그리고 x가 소수가 아닌 경우를 생각해 보자. x는 p와 q의 합성수가 될 것이므로 x = p * q 이렇게 써볼 수 있다.

그럼 정리하면 다음과 같다.

a * a = p * q

그러면 아래 세 가지 케이스만 존재하게 된다.

  1. 만약 p > a가 되는 경우, q < a가 된다.
  2. 만약 p = a가 되는 경우, q = a가 된다.
  3. 만약 p < a가 되는 경우 ,q > a가 된다.

이 내용을 통해 확인할 수 있는 것은 항상 p나 q 둘중 하나는 a보다 작다는 것이다. 그리고 a는 x의 제곱근이므로, 소수를 판별하기 위해 나눗셈을 하는 범위를 더욱 더 줄일 수 있다.

  1. 소수 리스트 l을 생성하고 여기에 2를 추가한다.
  2. 3~100사이의 홀수 n을 선택한다.
  3. n을 소수 리스트에 포함된 수 중 2~sqrt(n)의 모든 소수로 나누어본다.
  4. 나누어 떨어지지 않는다면 소수 리스트에 n을 추가한다.
  5. 나누어 떨어진다면 다른 홀수 n을 선택하고 다시 진행한다.