화 웨 이 oj 소수 배우자


, “ ”, 2 5、6 13, 。 , N(N ) “ ”, , 4 :2,5,6,13, 5 6 “ ”, 2 5、6 13 “ ”, “ ” “ ”, “ ”。

:

N(N≤100), 。 , [2,30000]。

:

K, “ ” “ ” 。


입력
입력 설명 1 짝수 n 2 입력 정수 n 개 입력
출력
구 하 는 '최선 의 방안' 은 '소수 동반자' 의 대 수 를 구성한다.
샘플 입력
4 2 5 6 13
샘플 출력
2
이 문제 에 대해 저 는 제목 의 본 의 는 헝가리 알고리즘 을 사용 하여 가장 일치 하 는 문 제 를 계산 하 는 것 이 라 고 생각 합 니 다. 두 개의 수의 합 이 하나의 소수 라면 반드시 홀수 와 짝수 의 조합 이기 때문에 두 개의 집합 으로 나 누 어 이분 도의 가장 큰 일치 문 제 를 구 할 수 있 습 니 다. 그러나 블 로 거들 은 그 당시 에 도 많은 생각 을 하지 않 았 습 니 다.모든 가능성 을 다 배열 해서 토론 했다.이것 은 가장 직접적인 생각 입 니 다. 다음은 c + + 실 현 된 소수 배우자의 코드 입 니 다.
#include <iostream>
#include <algorithm>

using namespace std;
int maxx = 0;
int main(){
	bool sushu(int x,int y);
	void permutation(int* str,int length) ;

	int n;
	cin >> n;
	int * pi = new int[n];
	for (int i = 0; i < n;i++)
		cin >> pi[i];

	permutation(pi,n);
	cout << maxx << endl;
	return 0;
}

bool sushu(int x,int y){
	int i,N;
	N = x + y;
	int flag=true;
	if (N==1) return 0;
	if (N==2) return 1;
	for (i=2;i<=sqrt(N);i++){
		if (N%i==0) 
		{
			flag=false;
			break;
		}
	}
	return flag;
}
void permutation(int* str,int length)  
{  
	int count = 0;
    sort(str,str+length);  
    do  
    {  
		for(int i=0;i<length;i+=2)  {
			if (sushu(str[i],str[i+1]))
				count++;
		}
		if (maxx < count)
			maxx = count;
		count = 0;
    }while(next_permutation(str,str+length));  
}  
next_permutation()   c++          ,          ,        。

좋은 웹페이지 즐겨찾기