문제 개요
양의 정수 n이 입력으로 주어졌을 때, 각 쌍의 합(i+j)이 소수이면서 n보다 작고, i != j이며 i와 j가 모두 1 이상이라는 조건을 만족하는 모든 숫자 쌍 (i, j)의 개수를 구하는 것이 목표입니다.
예를 들어 n이 4라면 가능한 쌍은 (1, 2) 하나뿐입니다. 1+2=3은 소수이고 4보다 작으며, 1과 2는 모두 1 이상이기 때문입니다.
예제로 이해하기
입력 − n=7
출력 − 합이 소수이고 n보다 작은 쌍의 개수: 3
설명 − 가능한 쌍은 (1, 2), (1, 4), (2, 3)입니다. 각각의 합인 3, 5, 5는 모두 소수이며 7보다 작습니다.
입력 − n=10
출력 − 합이 소수이고 n보다 작은 쌍의 개수: 6
설명 − 가능한 쌍은 (1, 2), (1, 4), (2, 3), (1, 6), (2, 5), (3, 4)입니다. 각각의 합인 3, 5, 5, 7, 7, 7은 모두 소수이며 10보다 작습니다.
접근 방법
이 접근 방식에서는 먼저 check_prime(bool check[], int temp) 함수 안에서 선드람의 체(Sieve of Sundaram)를 사용하여 n보다 작은 모든 소수를 찾습니다.
또한 각 홀수 temp에 대하여, 합이 temp가 되는 서로 다른 쌍의 개수는 temp/2입니다. 2를 제외한 모든 소수는 홀수이므로, n보다 작은 소수를 찾을 때마다 temp/2를 쌍의 개수에 더해 주면 됩니다.
- 변수 n을 입력으로 받습니다.
- prime_pair(int n) 함수는 n을 매개변수로 받아 합이 소수이고 n보다 작은 쌍의 개수를 반환합니다.
- 초기 count 값을 0으로 설정합니다.
- 선드람의 체는 입력 n에 대해 2*n+2 미만의 소수를 생성하므로, n을 반으로 줄여 temp_2에 저장합니다.
- (i + j + 2*i*j) 형태의 수들을 표시하기 위해 길이가 temp_2인 배열 Check[]를 생성하고, 모든 요소를 false로 초기화합니다.
- check_prime(bool check[], int temp) 함수를 사용하여 (i+j+2*i*j) 형태이면서 그 합이 temp보다 작은 수들에 대해 check[]를 true로 설정합니다.
- for 루프를 사용해 인덱스 i=0부터 i<temp_2까지 Check[]를 순회합니다.
- check[i]가 false인 경우, 소수는 temp = 2*i + 1이 됩니다.
- 합이 temp가 되는 쌍의 개수는 temp/2입니다.
- count에 temp/2를 더합니다.
- for 루프가 종료되면 합이 소수이면서 n보다 작은 전체 쌍의 개수를 구할 수 있습니다.
- count를 결과로 반환합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
void check_prime(bool check[], int temp){
for (int i=1; i<=temp; i++){
for (int j=i; (i + j + 2*i*j) <= temp; j++){
check[i + j + 2*i*j] = true;
}
}
}
int prime_pair(int n){
int count = 0;
int temp;
int temp_2 = (n-2)/2;
bool check[temp_2 + 1];
memset(check, false, sizeof(check));
check_prime(check, temp_2);
for (int i=1; i <= temp_2; i++){
if (check[i] == false){
temp = 2*i + 1;
count += (temp / 2);
}
}
return count;
}
int main(){
int n = 10;
cout<<"Count of pairs with sum as a prime number and less than n are: " <<prime_pair(n);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Count of pairs with sum as a prime number and less than n are: 6