function getPrimeNumbers(max) {
// A list of booleans where index 2 being true corresponds to 2 being prime
var isPrime = []; // Initial population of isPrime
for (var i = 0; i < max; i += 1) {
if (i != 0 && i != 1) {
isPrime.push(true);
}
else {
isPrime.push(false);
}
}
// Iterate over entire list
// Element => true if index is prime else false
for (var i = 0; i < max; i += 1) {
if (isPrime[i]) {
for (var j = i + i; j < max; j += i) {
isPrime[j] = false;
}
}
}
var primes = [];
// Assemble list of primes
for (var i = 0; i < max; i += 1) {
if (isPrime[i]) {
primes.push(i);
}
}
return primes;
}
이 외에도 앳킨의 체(Sieve of Atkin), 그리고 밀러-라빈 소수성 테스트(C++로 보기)와 같은 확률적 소수성 테스트에 대한 매력적인 접근 방식 등 주어진 영역에서 소수를 발견하기 위한 다른 많은 접근 방법이 개발됐다. 밀러-라빈은 속도는 빠르지만(O(k log3 n)) 확률적인 속성으로 인해 가끔 거짓 양성이 발생할 수 있다.
소수를 찾기 위한 알고리즘은 잘 알려졌고, 코딩으로 작성하기도 간단하다. 처음의 단순함과 수학 천재들의 1,000년에 걸친 관심에도 불구하고 소수의 특징과 본질은 여전히 신비로운 영역으로 남아 활발한 연구가 이뤄지고 있다는 점은 생각해보면 놀라운 일이다.
리만 가설
수학에서 가장 흥미로운 미해결 문제 중 하나는 리만 가설(Riemann Hypothesis)이다. 이를 계산하기 위한 코드베이스를 깃허브에서 다운로드할 수 있다.
리만은 가우스의 학생이었다. 가우스라는 이름은 어도비 포토샵과 같은 소프트웨어에 있는 “가우시안 블러(Gaussian blur)”를 통해서도 아마 들어봤을 것이다. 가우스는 소수의 발견을 추정하는 함수를 고안했는데, 지금은 이 함수를 소수 정리(Prime Number Theorem)라고 한다. 리만의 함수는 제타 함수로, 복소수를 무한 급수에 통합해 가우스 정리의 정확도를 높인다. 리만 가설은 숫자의 근본적인 동작을 들여다보는 가설이다. 이것이 컴퓨터 과학에 미치는 영향은 아직 다 밝혀지지 않았다. 이 가설의 증명은 이론 수학에서 가장 많은 노력이 이뤄지고 있는 부분이다.
