문제번호

1929

package Main;

import java.util.Scanner;

public class Main {
	public static StringBuilder sb = new StringBuilder ();
	
	public static void main(String[] args) {
	
		Scanner in = new Scanner(System.in);
		
      	// 시작값 끝값 입력 
		int pre = in.nextInt();
		int post = in.nextInt();
		
      	// 시작값부터 끝값까지 find함수 반복
		for (int start = pre ;start <= post;start++) {
			find(start);
		}
      	// 출력
		System.out.println(sb);
	}
	
	static void find (int value) {

      	// 2 미만은 소수가 없으므로 return
		if (value < 2) {
			return;
		}
		
      	// 값이 2인 경우 2 하나이므로 2 + return
		else if (value == 2) {
			sb.append(2+"\n");
			return;
		}
		
      	// 2이상 루트 value 값 까지 탐색 이때 value / i 의 나머지가 없는 경우 return
		for (int i = 2 ; i <= Math.sqrt(value);i++) {
			if (value % i == 0) {
				return;
			}
		}
		
      	// 위의 반복문을 거친 후 return 되지 않았다면 소수이므로 sb에 추가
		sb.append(value+"\n");
		return;
	}
}

문제

https://www.acmicpc.net/problem/1929

풀이

• 에라토스테네스의 체를 활용해야하는 문제이다.

  • 2부터 해당 수 전까지 해당 수가 나누어 떨어지지 않는다면 그 수는 소수이다.

• 탐색범위를 루트를 사용하여 좁힐 수 있다.

  • 특정값이 소수가 아닌경우 루트를 씌운 값은 그 값 이하의 자연수로 나누어 떨어진다.
    그러나 소수인 경우 나누어 떨어지지 않는다.
    이 원리를 이용하여 탐색 범위를 좁힐 수 있다.