진단테스트 - 기초 3단계 (소수 문제)

배열, 루프와 함수를 자유롭게 다룰 수 있는 단계입니다. 이 단계를 마친 사람은 객체로 넘어가기 위한 충분한 준비가 되었네요.

[문제 기초 3-1] 소수인지 판정하기

소수인지 판정하는 isPrime(n) 함수를 만들어 봅시다. 숫자를 반복해서 입력받아 소수인지 아닌지를 판정하는 함수입니다. 소수는 1과 자신 이외에 인수가 없는 자연수를 말합니다. 2부터 루트 n까지의 자연수로 차례로 n을 나누어 떨어지는 수가 있으면 소수가 아니고 나누어 떨어지는 수가 하나도 없으면 n은 소수가 됩니다.

Math.sqrt(n);  // n의 제곱근을 구하는 라이브러리 함수입니다.

for (int i = 2; i < Math.sqrt(n); i++)
   if (n % i == 0)
      return false;
return true;

[문제 기초 3-2] 계산된 소수를 모으기

앞의 방법은 아주 큰 수를 계산할 때는 비효율적일 수 있습니다. 왜냐하면 어떤 수가 3으로 나누어 떨어지는가 검사한 다음에 6, 9, 12, 15, ...를 계속 다시 나머지 연산을 하게 되기 때문입니다. 즉 우리는 어떤 수로 나누어 떨어지지 않는다는 것을 알면 그 다음에 그 수의 배수는 다시 검사할 필요가 없습니다. 이것이 에라토스테네스라는 사람이 가장 먼저 발견한 소수를 구하는 방법입니다.

이 방법을 사용하기 위해서는 지금까지 검사된 k개의 소수를 배열에 모아두고 다음 수가 지금까지 알고 있는 소수의 배수라면 건너뛰는 방법입니다. 이 방법의 알고리듬은 다음과 같습니다. 

int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71};
int k = 20;
boolean isPrime(int n) {
   for (int i = 0; i < k; i++) {
      if (primes[i] > Math.sqrt(n))
         return false;
      if (n % primes[i] == 0)
         return false;
   }
   return true;
}

이 방법을 위해서는 primes 배열을 모아 두어야 하는 문제가 있고 또 그 배열에 있는 제일 큰 수의 제곱보다 큰 값이 들어오면 이것만으로는 해결할 수 없다는 점이 문제입니다.

[문제 기초 3-3] 이미 알고 있는 소수의 배열에서 다음 소수를 찾는 문제를 생각해 봅시다. 지금까지 소수 배열에 k개가 들어있다면 다음 소수는 제일 큰 소수 +1부터 차례로 숫자를 검사하면서 소수 배열에 있는 값으로 나누어보면 됩니다. 

int findNextPrime(int[] primes, int k) {
   int n = primes[k-1]+1;
   Outer:
   while (true) {
      for (int i = 0; i < k; i++)
         if (n % primes[i] == 0) {
            n++;
            continue Outer;
         }
      break;
   }
   return n;
}

이 코드는 독특한 구조를 가집니다. n이 i번째 소수로 나누어 떨어지면 소수가 아니므로 다음 수 n++로 넘어가면 됩니다. (continue Outer;는 바깥 루프로 continue시켜 줍니다.) 이 루프는 반드시 종료한다는 것이 보장되는데 왜냐하면 소수는 무한개이므로 반드시 언젠가는 소수가 발견될 것이기 때문입니다. 이렇게 돌려받은 소수를 배열에 추가하면 계속 다음 소수를 구할 수 있습니다.

void findAllPrimes(int n) {
   int[] primes = new int[n];
   int k = 1, p = 2;
   primes[0] = p;
   while (true) {
      p = findNextPrime(primes, k);
      if (n < p) break;
      primes[k++] = p;
   }
   System.out.printf("%d 이하의 소수 : ", n);
   for (int i = 0; i < k; i++)
      System.out.printf("%5d", primes[i]);
}      

[문제 기초 3-4] 이번에는 사용자가 입력한 임의의 수 n 이하의 모든 소수를 찾는 것을 2 미만의 값이 들어올 때까지 반복하는 문제를 생각해 봅시다. 여기서도 위에서 정의한 findNextPrime을 사용할 수 있으나 다음의 두 가지 경우로 나누어 생각해 볼 수 있습니다.

1. n이 이미 찾은 소수보다 작은 경우 - 배열에서 n 이하의 소수를 모두 출력
2. n이 지금까지 찾은 소수 중 제일 큰 값보다 큰 경우 - n까지의 소수를 차례로 찾아서 차례로 배열에 저장하고 모두 출력

여기서 배열의 크기를 어떻게 정할 것이냐가 우선 첫번째 결정해야 할 문제입니다. 소수의 개수는 무한하므로 무한개의 배열이 아닌 이상 언제든 배열의 크기를 넘어갈 가능성이 있습니다. 그런 경우는 배열의 ArrayIndexOutOfBoundsException이 발생할 것입니다.

int[] primes = new int[500];
int k = 1;
void mymain() {
   primes[0] = 2;
   int n = 0;
   while (true) {
      n = scan.nextInt();
      if (n < 2) break;
      findAllPrimes(n);
   }
}

void findAllPrimes(int n) {
   System.out.printf("%d 이하의 소수 : ", n);
   if (primes[k-1] > n) {
      for (int i = 0; i < k; i++) {
         if (primes[i] > n) break;
         System.out.printf("%5d", primes[i]);
      }
      System.out.println();
      return;
   }
   while (true) {
      p = findNextPrime(primes, k);
      if (n < p) break;
      primes[k++] = p;
   }

   for (int i = 0; i < k; i++)
      System.out.printf("%5d", primes[i]);
   System.out.println();
}