소수

과제: 제공된 인자에 대해 그 인자 이하의 모든 소수를 반환하는 함수를 작성하시오.

소수란 1과 자신으로만 나눌 수 있는 양의 정수를 뜻한다. 따라서 2와 3은 소수이나, 4는 아니다. 왜냐하면 4는2로도 나눌 수 있기 때문이다. 다음은 1에서 시작해서 15개의 소수를 나열한 것이다.

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

계산을 통해 모든 소수를 나열할 수 있는 공식은 현재 알려져 있지 않다. 필자가 글을 쓰는 이 시점에 소수로 알려진 가장 큰 수는 2 57,885,161–1이다. 전자 프런티어 재단Electronic Frontier Foundation[1]에서는 아주 큰 소수를 발견하는 것에 대해 상을 주겠다고 제시한다.

[1] https://www.eff.org/