[Algorithm] 에라토스테네스의 체

💙 에라토스테네스의 체?

• 고대 그리스 수학자 에라토스테네스가 발견한 소수 판별 알고리즘

🤍 약수(Divisor)?

• 1과 자기 자신 외 약수를 가지지 않는 1보다 큰 자연수

🤍 소수(Prime Number)?

• 어떤 수를 나눠떨어지게 하는 수

💛 알고리즘

1. 2부터 소수를 구하고자 하는 구간의 모든 수 나열 (맨 처음 회색)
2. 2 == 소수 (빨간색)
   1. Prime numbers: 2
   2. 자기 자신을 제외한 2의 배수 제거
3. 남아있는 수 중, 3 == 소수 (초록색)
   1. Prime numbers: 2 3
   2. 자기 자신을 제외한 3의 배수 제거
4. 남아있는 수 중, 5 == 소수 (파란색)
   1. Prime numbers: 2 3 5
   2. 자기 자신을 제외한 5의 배수 제거
5. 남아있는 수 , 7 == 소수 (노란색)
   1. Prime numbers: 2 3 5 7
   2. 자기 자신을 제외한 7의 배수 제거
6. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남게 됨

💚 코드 구현

🤍 문제: 소수 판별

• 1 이상의 자연수를 입력받음
• 소수이면 true, 아니면 false 리턴

🤍 반복문 사용

public class Eratosthenes1 {
	public boolean isPrime(int num) {
    
    if(num == 1) 
      return false;

    for(int divisor = 2; divisor < num; divisor++) { // 나눠떨어지는 수가 있는지 없는지 확인
    // 초기화를 2부터 하는건 1이랑 자기 자신 외 나눠지는게 없어서

      if(num % divisor == 0)
        return false;
    }

    return true;
  }
}

🤍 Math 클래스 사용

public class Eratosthenes2 { 
	public boolean isPrime(int num) {
    
		// Math 클래스 사용
    int sqrt = (int)Math.sqrt(num);

    if(num == 1)
      return false;

    for(int i = 2; sqrt >= i; i++) {
      if(num % i == 0)
        return false;
    }

    return true;
	} 
}

💜 Ref.

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