[알고리즘] 에라토스테네스의 체(소수를 찾는법)

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

---

◼︎ 개념

소수를 구하는 알고리즘인 에라토스테네스에 대해 알아보자

 

소수란 무엇인가?

- 소수: 1보다 큰 정수 1과 자기 자신으로만 나누어지는 수

라고 되어있으며 이러한 소수에는 2, 3, 5, 7...이 존재한다.

 

일반적으로 숫자를 입력받아 1~n사이의 소수를 구하라는 문제를 받았을 때

2로나누어 나머지가 존재하면 "소수", 나머지가 존재하지 않으면 "정수"로 간단하지만 반복을 많이 하는 코드를 작성해서 구현하였다.

 

하지만 에라토스테네스의 체를 이용하면 아주 효율적으로 소수를 찾아낼 수 있다.

 

◼︎ 원리

1~120의 정수사이에 소수를 찾는 방법은 다음과 같다

1. 1은 소수가 아니므로 제외한다

2. 2부터 순서대로 하나씩 숫자를 확인

  - 2는 소수

     - 2의 배수는 소수가 아니므로 모두 제외

  - 3은 소수

     - 3의 배수는 소수가 아니므로 모두 제외

  - 4는 2의 배수에서 제외된 상태

  - 5는 소수

     - 5의 배수는 소수가 아니기 때문에 제외

....이러한 과정을 반복하며 찾아나가다

 

120은 11^2(11의 제곱) 보다 작다는 계산이 나오게된다.

 

이때 11을 제외한 이전에 발견된 소수들의 배수를 모두 제거하면 1~120사이의 소수만 남겨낼 수 있다.

 

◼️ 구현

import java.util.ArrayList;
import java.util.Scanner;
 
public class Eratos01 {
  
  /*
   * # 개념
   * 에라토스테네스의 체는 고대 그리스 수학자인 에라토스테네스가 발견한 소수를 찾는 방법이다
   * 
   * # 알고리즘
   * 0,1을 제외한 소수를 찾고싶은 구간의 수를 나열 
   * EX) 0~120구간까지
   * - 2 제외, 이후 2의 배수 모두 삭제
   * - 3 제외, 이후 3의 배수 모두 삭제
   * - 4 2의 배수여서 삭제 됨
   * ...
   * - 위의 과정을 반복, 11*11 > 120이므로 
   * 11보다 작은 소수들의 배수만 지우고 남은 숫자들은 모두 소수이다
   */
  public static void main(String[] args) {
      // 구현해보기
      //-소수 판별을 위한 Boolean
      ArrayList<Boolean> isPrimeList;
 
      //숫자구간 입력받기
      Scanner sc = new Scanner(System.in);
      System.out.print("숫자입력: ");
      int n = sc.nextInt();
      sc.close();
      //0,1이면 종료
      if(n <= 1) return;
 
      //n+1만큼 할당 why? 2부터 시작되도록
      isPrimeList = new ArrayList<Boolean>(n+1);
      //0,1번째 미리 false처리 
      isPrimeList.add(false);
      isPrimeList.add(false);
      //2~입력 수 까지는 소수(true)로 임시 설정해놓기
      for(int i = 2; i <= n; i++) {
        isPrimeList.add(i,true);
      }
 
      // System.out.println("isPrimeList(2): " + isPrimeList.get(2));
      //배수지워나가기
      for(int i = 2; (i*i) < n; i++){//2부터
        if(isPrimeList.get(i)){ //무슨용도지->미리 true로 설정해놓은 것을 가여오는 역할
            for(int j = i*i; j <= n; j += i){//j+=i => 중요
              isPrimeList.set(j, false);     //j+-i의 배수로 만들어주는 과정모두 false - 
            }
        }
      }
 
      //출력하기
      StringBuffer sb = new StringBuffer();
      sb.append('{');
      for(int i = 0; i <= n; i++){
        if(isPrimeList.get(i) == true){
          sb.append(i);
          sb.append(",");
        }
      }
      //sb.length() -> 마지막 ','를 지우고 출력하기 위해서
      sb.setCharAt(sb.length()-1, '}');//문자열로변환
      System.out.println(sb.toString());      
 
  }
 
}