어떤 수를 나누었을 때 나머지가 0이 되는 수. 즉 나누어 떨어지는 수(단, 약수는 정수이다)
모든 자연수는 최소한 1과 자기 자신을 약수로 갖는다.
1보다 큰 자연수 중 1과 자기 자신밖에 약수가 존재하지 않는 자연수를 소수(Prime (Number)/ 소수(素數))라고 한다.
옛날 어느 왕국의 성벽에는 1번부터 100번까지 100개의 성문이 있는데, 매일 100명의 문지기가 다음과 같은 방법으로 문을 여닫는다고 한다.
1번 문지기는 모든 문을 열어 놓는다.
2번 문지기는 2의 배수에 해당하는 문이 열려 있으면 닫고, 닫혀 있으면 연다.
이와 같은 방법으로 n번 문지기는 n의 배수에 해당하는 문이 열려 있으면 닫고, 닫혀 있으면 연다.
그렇다면, 100명이 모두 문을 여닫았을 때, 열려 있는 문은 몇 번 문인가?
1번 문지기가 모든 문을 열어 놓으므로 처음에는 모든 문이 닫혀 있다고 가정하자.
n번 문은 n의 약수에 해당하는 문지기에 의해 열리고 닫힐 것이다.
문이 열려 있으면 그 문을 여닫은 문지기가 홀수 명이라는 뜻이고, 닫혀 있으면 짝수 명이라는 뜻이므로, 열려 있는 문에 해당하는 번호의 약수의 개수는 홀수일 것이다.
따라서 최종적으로 제곱수에 해당하는 1, 4, 9, ..., 100번의 10개의 문이 열려 있을 것이다.