[swea-D3] 27668. 소피 제르멩 소수

[swea-D3] 27668. 소피 제르멩 소수

🙋‍♂️ 문제 설명

1보다 큰 자연수 중에서 1과 자기 자신만을 약수로 가지는 수를 소수라고 한다.

예를 들어 2, 3, 5, 7, 11은 소수이며, 1은 소수가 아니다.

소수 p에 대하여 2p + 1 역시 소수라면,
p를 소피 제르맹 소수(Sophie Germain Prime) 라고 한다.

예시

• p = 2일 때, 2p + 1 = 5이므로 2는 소피 제르맹 소수이다.
• p = 11일 때, 2p + 1 = 23이므로 11은 소피 제르맹 소수이다.
• 반면 p = 7일 때, 2p + 1 = 15는 소수가 아니므로 7은 소피 제르맹 소수가 아니다.

여러 개의 정수 구간 [L, R]이 주어질 때, 각 구간에 포함되는 소피 제르맹 소수의 개수를 구하여라.

[L, R]은 L 이상 R 이하의 범위를 의미한다.

---

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

이후 T개의 테스트 케이스가 주어진다.

각 테스트 케이스는 한 줄로 구성되며, 두 정수 L과 R이 공백을 사이에 두고 주어진다.

• L은 탐색할 구간의 시작 값이다.
• R은 탐색할 구간의 끝 값이다.

제한 조건

• 1 ≤ T ≤ 10
• 1 ≤ L ≤ R ≤ 1,000,000

---

입력 예시

5
1 10
10 30
1 100
50 100
100 1000

---

출력 예시

#1 3
#2 3
#3 10
#4 3
#5 27

내 설계

// 1. main 
	// 1-1. 반복문
		// 1-1-a. 만약 둘다 소수라면 cnt++

// 2. 함수 (소수인가?)
	// 2-1. 2부터 제곱근까지 한번이라도 나눠지면 소수 아님
	// 2-2. 그외 true

// 3. 함수 (제곱근 구하기)
	// 이진탐색 (오버플로우 조심)

✅ 정답 코드

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;


public class Solution {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc < T+1; tc++) {
			String[] se = br.readLine().split(" ");
			int s = Integer.parseInt(se[0]);
			int e = Integer.parseInt(se[1]);
			
			int cnt = 0;
			for (int i = s; i < e+1; i++) {
				// 1. 소수 아니면 skip
				if (i < 2 || (i >= 3 && i % 2 == 0)) continue;
				
				// 2. 그외 검사
				if (is_prime(i) && is_prime(2*i + 1)) cnt++;
			}
			// 4. 출력
			System.out.println("#" + tc + " " + cnt);
		}
	}
	
	// 3. 함수 (소수인가?)
	static boolean is_prime(int num) {
		int my_sqrt = get_sqrt(num);
		// 한번이라도 나눠지면 소수 아님
		for (int i = 2; i < my_sqrt + 1; i++) {
			if (num % i == 0) return false;
		}
		// 3-2. 그외 true
		return true;
	}
	
	
	// 4. sqrt 구하는 함수
	static int get_sqrt(int num) {
		int left = 1;
		int right = num;
		int ans = 0;
		
		while (left <= right) {
			int mid = (left + right) / 2;
			// 오버플로우 방지 mid * mid > n
			if (mid > num/mid) {
				right = mid-1;
			}
			else if (mid <= num/mid) {
				ans = mid;
				left = mid + 1;
			}
		}
		return ans;
	}
	
	
}