소수(Prime Number) 구하는 방법 (내용 수정 있음)

다들 잘 아시겠지만 소수(Prime Number)는 정수들 주에서 약수가 1과 자신뿐인 숫자(0, 1은 제외)를 의미합니다. 자주는 아니지만 간혹 이런 값들을 구해야 할 경우가 생기는데, IDL에서는 소수를 구해주는 PRIMES라는 자체 내장함수가 있긴 합니다만 아주 단순한 기능만 제공합니다. 예를 들어 PRIMES(10)을 구하라고 하면, 처음부터 10개의 소수들을 구해줍니다. 즉 2, 3, 5, ...., 29의 값들을 돌려주게 됩니다. 하지만 특정 범위의 소수들, 예를 들어 100과 200 사이의 소수들만 구해준다든지 하는 부가적인 기능은 없습니다. 따라서 좀 더 유연한 방식으로 소수들을 찾을 수 있는 방법을 소개하고자 합니다. 이는 비교적 간단한(?) 코딩으로 구현이 가능한데요. 다음은 1부터 50까지의 정수들 중 소수에 해당되는 값들만 추출하여 소수들만으로 구성된 새로운 배열을 얻는 프로그램입니다.

 

a = INDGEN(50)+1; 1부터 50까지의 정수들로 이루어진 배열
p = []; 추출된 소수들만 담게 될 초기 배열
FOR i = 0, N_ELEMENTS(a)-1 DO BEGIN
  value = a[i]
  IF value LE 3 OR MIN(value MOD [2:FIX(SQRT(value))]) THEN p = [p, value]
ENDFOR
PRINT, p

여기서 핵심은 반복문안에서 소수에 해당되는 값만 추출하는 논리식입니다. 좀 복잡해보이긴 하는데, 대상이 되는 값의 제곱근을 구하고, 2부터 제곱근까지의 값들로 원래 값을 나누었을 때 나머지들 중 최소가 0인 경우는 1과 자신외에 다른 약수가 존재하지 않는다는 의미로 이런 값들만 골라내는 과정이라고 보면 됩니다. 최소가 0이 아니라면 뭔가 다른 약수가 존재한다는 의미가 되어서 소수에 해당되지 않겠죠. 그렇게 추출된 값들만 p라는 배열로 새로 모았다고 보면 됩니다. 어쨌든 위의 내용을 실행하면 다음과 같이 소수들만 출력됩니다.

 

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

그리고 프로그램의 맨 처음 줄에 있는 원래의 대상 배열은, 앞서 올린 게시물에서 언급했던 새로운 배열 생성법을 사용하면 다음과 같이 적을 수도 있습니다(8.3 또는 그 이후 버전에만 해당).

 

a = [1:50]

 

그리고 다른 범위 정수들에 대하여 똑같은 작업을 할 경우에는 이 a의 내용만 바꿔주면 됩니다. 예를 들어, 100부터 150까지의 정수들 중 소수인 것들만 골라내는 경우라면 맨 첫 줄이 다음과 같이 바뀌면 되겠지요.

 

a = [100:150]

 

이렇게 했을 경우에는 다음과 같이 이 범위내의 소수들만 출력됩니다.

 

     101     103     107     109     113     127     131     137     139     149

이와 같은 방식으로 우리가 원하는 범위내의 정수들에 대하여 소수들을 추출하는 것이 가능하다는 점 참조하시면 되겠습니다.