[알고리즘] 에라토스테네스의 체

소수는 1보다 큰 자연수 가운데 1과 자기 자신만을 약수로 가지는 수를 뜻한다.

7의 경우 자기자신(7)과 1을 약수로만 가지기 때문에 소수이지만, 4의 경우 자기자신(4)와 1 이외에도 2라는 약수를 포함하기 때문에 소수가 아니다.

 

그렇다면 만약 20이하의 숫자중에서 소수를 구하는 방법을 어떻게 코드로 옮길 수 있을까 ?

아이디어는 20이하의 숫자 n을 검사하면서, 2부터 n-1까지 수 중에서 n을 나누었을 때 나머지가 0인 숫자가 존재하면 해당 숫자는 소수가 아니게 된다.

 

import java.util.Scanner;
public class Main{
    public static void main(String[] args){

      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
       
      boolean isPrime;
      
      for(int i=2;i<=n;i++){
        isPrime=true;
        for(int j=2;j<i-1;j++){
          if(i%j==0){
            isPrime=false;
          }
        }
        if(isPrime){
          System.out.println(i+"는 소수입니다.");
        }else{
          System.out.println(i+"는 소수가 아닙니다.");
        }
      }
    }
}  

첫번째 for문에서 1을 제외한 20이하의 숫자들을 반복하고,

두번쨰 for문에서는 각각의 20이하의 숫자중에서 1과 n을 제외한 숫자에서 n을 나누었을 때, 만약 나머지가 0이면 해당 숫자는 소수가 아니게 된다.

 

하지만 이 방법은 문제가 있다. 20이하의 숫자들을 반복하면서 각각의 숫자에 대해 1부터 다시 반복을 해야 하기 때문에,  O(n^2)의 시간복잡도를 가지는데 숫자가 커졌을 때, 연산을 하는데 많은 시간을 잡아먹게 된다.

 

 

위의 사진은 이 글의 주제인 에라토스테네스의 체를 설명한 그림이다.

그림에서 2를 제외하고 2의 배수를 모두 체크해주고, 3을 제외하고 3의 배수를 모두 체크해준다. 4는 이미 2의 배수에서 체크 되었기 때문에 건너 뛰고 다음 5를 제외하고 5의 배수를 체크해준다.......

 

n의 배수를 지워줬는데, 가만 생각해보면 n의 배수란 말은 해당 숫자가 n을 약수로 가지고 있다는 말이 된다. 2의 배수는 4 6 8...인데, 모두 2를 약수로 가지고 있고 이 값들을은 모두 소수가 아니게 된다.

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        boolean[] arr = new boolean[101];

        for (int i = 2; i <= Math.sqrt(100); i++) {
            for (int j = i + i; j <= 100; j += i) {
                arr[j] = true; // true인 부분은 소수가 아닌 부분
            }
        }

        if (arr[n] == false) {
            System.out.println(n + "은 소수입니다.");
        } else {
            System.out.println(n + "은 소수가 아닙니다");
        }

    }
}

처음 배열을 생성해놓고, 각각 i값을 시작으로 i의 배수만큼 증가하면서 해당 위치에서 true로 바꿔주는데, arr배열에서 true인 부분은 소수가 아닌 부분을 의미합니다.