🦖 에라토스테네스의 체

소수를 찾는 방식

---

🌳 알고리즘

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
2. 2는 소수이므로 오른쪽으로 이동하고 자기자신을 제외한 2의 배수를 모두 지운다.
3. 남아있는 수 중에서 3은 소수이므로 오른쪽으로 이동하고 자기자신을 제외한 3의 배수를 모두 지운다.
4. 남아있는 수 중에서 5는 소수이므로 오른쪽으로 이동하고 자기자신을 제외한 5의 배수를 모두 지운다.
5. 남아있는 수 중에서 7은 소수이므로 오른쪽으로 이동하고 자기자신을 제외한 7의 배수를 모두 지운다.
6. 위의 과정을 반복하면 구하는 구간의 모든 소수를 구할 수 있다.

위 그림의 경우 11의 제곱이 120보다 크기때문에 11보다 작은 수의 배수들만 지워도 충분하다.

JAVA로 구현하기

public class Eratos {
	public static void main(String[] args) {
		// ArrayList로 구현
		ArrayList<Boolean> primeList;

		// 사용자로부터의 콘솔 입력
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();

		// n <= 1 일 때 종료
		if(n <= 1) return;

		// n+1만큼 할당
		primeList = new ArrayList<Boolean>(n+1);
		// 0번째와 1번째를 소수 아님으로 처리
		primeList.add(false);
		primeList.add(false);
		// 2~ n까지 소수로 설정
		for(int i=2; i<=n; i++ )
			primeList.add(i, true);

		// 2부터  ~ i*i <= n
		// 각각의 배수들을 지워간다.
		for(int i=2; (i*i)<=n; i++){
			if(primeList.get(i)){
				for(int j = i*i; j<=n; j+=i) primeList.set(j, false);
				//i*i 미만은 이미 처리되었으므로 j의 시작값은 i*i로 최적화할 수 있다.
			}
		}
		StringBuffer sb = new StringBuffer();
		sb.append("{");
		for(int i=0; i<=n; i++){
			if(primeList.get(i) == true){
				sb.append(i);
				sb.append(",");
			}
		}
		sb.setCharAt(sb.length()-1, '}');

		System.out.println(sb.toString());

	}
}

point❗️ 배수들은 소수가 아니기때문에 배수들의 값을 지워나가는 방식으로 소수를 구하는 것!!

---

🍀 관련 문제

프로그래머스 Lv1. 소수 찾기

---

📑 References

위키백과 - 에라토스테네스의 체