• 소수를 판별하는 알고리즘
• 소수를 대량으로 빠르고 정확하게 구하는 방법
• 소수를 판별할 범위만큼 배열을 할당하여, 해당하는 값을 넣어주고, 하나씩 지워나가는 방법을 이용한다.

1. 2 부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.

2. 소수가 되는 수의 배수를 지우고 남은 수는 소수가 된다.

   

   https://ko.wikipedia.org/wiki/에라토스테네스의_체

• 위 예시 코드

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());

	}

• 해당 분류 문제

4948번: 베르트랑 공준