1보다 큰 자연수로서 1과 그 수 자체 외의 약수를 가지지 않는 수. 예를 들면 2, 3, 5, 7, 11 등이다.

2 이외의 소수는 홀수이므로 홀소수라고 한다.

1 이외의 자연수로서 소수가 아닌 것 및 (-)부호가 붙은 것(±4, ±6 등)을 합성수(合成數)라 한다.

주어진 자연수 n이 소수인지 아닌지를 판정하려면 이하의 소수로 나누어 보면 알 수 있다.

즉, 나누어지지 않으면 소수이고 나누어지면 합성수이다.

예를 들어 997의 소수 여부를 판정 하려면 31<997<32(=31…)이므로 31 이하의 소수 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31로 997을 나누어 본다.

이 중 어느 것으로도 나누어지지 않으므로 997은 소수이다.

그러나 큰 자연수가 소수인지 아닌지를 판정하는 것은 일반적으로 쉽지 않다.

자연수 중에서 소수를 가려내는 에라토스테네스의 체(Eratosthenes sieve)라는 방법이 있는데, 이것도 위와 같은 원리를 따른 것이며 수가 크면 대단히 곤란하다.

그러나 소수 판정에 특히 편리한 방법으로 메르센수(數), 즉 M=2-1의 모양의 수에 대해서는 능률적인 판정법이 고안되어 컴퓨터를 이용해서 대단히 큰 소수까지도 확인할 수 있다.

이를테면 M=2-1은 1959년에, M=2-1과 M= 2-1은 61년에 각각 컴퓨터를 이용하여 소수임이 확인되었다.

M은 무려 1,332자리의 수이다.

소수에 대한 연구는 고대 그리스시대부터 시작되었다.

유클리드는《기하학 원본(Stoicheia)》에서 ① 1 이외의 자연수는 모두 소수의 곱으로 일의적으로 표시할 수 있다.

② 소수는 무한히 존재한다는 소수에 관한 중요한 정리를 기술했다.

그러나 그 후 오랫동안 이 방면의 연구는 진전을 보지 못하다가 19세기에 와서 C. F. 가우스는 소수의 분포, 즉 어떠한 규칙에 따라 소수가 자연수 중에 나타나는가 하는 문제를 고찰했다.

소수의 분포는 대단히 복잡하다.