입력으로 양수 n이 제공됩니다. 목표는 각 쌍이 소수이고 n보다 작은 합(i+j)을 갖도록 가능한 쌍(i,j)의 수를 찾는 것입니다. 또한 i !=j 및 i,j>=1 n이 4이면 (1,2)인 1쌍만 가능합니다. 여기서 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)에서 순다람의 체를 사용하여 n보다 작은 모든 소수를 찾을 것입니다.
또한 각 홀수 temp에 대해 합계 온도가 있는 고유한 쌍의 수는 temp/2가 됩니다.
2를 제외하고 모든 소수는 홀수이므로 n보다 작은 소수를 찾으면 쌍 수에 temp/2를 추가합니다.
-
변수 n을 입력으로 사용합니다.
-
Prime_pair(int n) 함수는 n을 취하고 sum이 소수이고 n보다 작은 쌍의 개수를 반환합니다.
-
초기 카운트를 0으로 합니다.
-
순다람의 체는 입력 n에 대해 2*n+2보다 작은 소수를 생성합니다. n을 절반으로 줄이고 temp_2에 저장합니다.
-
길이가 temp_2인 배열 Check[]를 만들어 형식( i+j+2*i*j )의 모든 숫자를 True로 표시합니다. 모든 요소를 false로 초기화합니다.
-
check_prime(bool check[], int temp) 함수를 사용하여 (i+j+2*i*j) 형식의 숫자에 대해 true로 check[]를 초기화합니다. 그리고 이 합계
-
이제 인덱스 i=0에서 i
-
각 검사[i]가 거짓이면 소수는 temp=2*i+1이 됩니다.
-
temp에 합산되는 쌍은 temp/2가 됩니다.
-
temp/2를 추가하여 계산합니다.
-
for 루프가 끝나면 합계가 소수이고 n보다 작은 총 쌍이 있습니다.
-
결과로 카운트를 반환합니다.
예시
#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