Day11에라토스테네스의 체

에라토스테네스의 체

• 소수를 찾는 방법
  1. 2부터 소수를 구하고자 하는 구간의 모슨 수를 나열한다.
  2. 2는 소수이므로 따로 뺀다.
  3. 자기 자신을 제외한 2의 배수를 모두 지운다.
  4. 남아있는 수 가운데 3은 소수이므로 3을 따로 뺸다.
  5. 자기 자신을 제외한 3의 배수를 모두 지운다
  6. 남아있는 수 가운데 5은 소수이므로 5을 따로 뺀다.
  7. 자기 자신을 제외한 5의 배수를 모두 지운다.
  8. 남아있는 수 가운데 7은 소수이므로 7을 따로 뺀다.
  9. 자기 자신을 제외한 7의 배수를 모두 지운다.
  10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.
•  

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

	}
}

ㅁ 백만 이하의 자연수 중 입력하여 그 값이하의 소수의 총 개수를 구하는 문제를 푸는데 에라토스테네스의 체 방식을 사용하지 않고 무작정 풀면 작동하는 시간이 한참 걸린다.
로직을 어떻게 작성하느냐에 따라 속도의 차이를 몸으로 느꼈다.

ㅁ 공부하며 점심을 먹으니 시간낭비를 조금 줄일 수 있어서 오후에 살짝 집중을 하지 못해도 그만큼 커버가 됐다.
다음주부터 더 어려워져서 힘들어질꺼라고 하는데 긴장감이 들면서 기대가 된다.