哥德巴赫猜想.cpp

八皇后问题的最好解法,利用回朔法的典型例子,还有其他几个好程序

#include <iostream>
#include <vector>
#include <iterator>
#include <cmath>

using namespace std;

int nextPrime(vector<int>&vPrime)

{
	int n=vPrime[vPrime.size()-1]+2;
	int m=(int)sqrt(2.0*n);
	for(int i=n;;i+=2)
	{
		vector<int>::const_iterator itr;
		for(itr=vPrime.begin();*itr<=m&&i%(*itr);++itr);
		if(*itr>m)
		{
			vPrime.push_back(i);
			return i;
		}
	}
}

bool find(vector<int>&vPrime,const int x)
{
	int i=0;
	int j=vPrime.size()-1;
	int m;
	while(i<=j)
	{
		m=(i+j)/2;
		if(x==vPrime[m])
			return true;
		else if(x>vPrime[m])
			i=m+1;
		else
			j=m-1;
	}
	return false;
}

bool split(vector<int>&vPrime,const int sum,int &x,int &y)
{
	vector<int>::reverse_iterator itr;
	for(itr=vPrime.rbegin(); 2*(*itr)>=sum; ++itr)
	{
		if(find(vPrime,sum-(*itr)))
	{
		x=*itr;
		y=sum-(*itr);
		return true;
	}
	}
	int p;
	while((p=nextPrime(vPrime))<=sum-3)
	{
		if(find(vPrime,sum-p))
		{
			x=p;
			y=sum-p;
			return true;
		}
	}
	return false;
}

void check(int n)
{
	vector<int>vPrime;
	int x,y;
	vPrime.push_back(2);
	vPrime.push_back(3);
    for(int i=6;i<n;i+=2)
	{
		if(split(vPrime,i,x,y))
			cout<<i<<"="<<x<<"+"<<y<<endl;
		else
			cout<<"Goldbach's conjecture is false "<<i<<"!"<<endl;
	}
}

int main()
{
	int n;
	do
	{
		cout<<"Input an even number(must>=6):";
		cin>>n;
		if(n>=6&&n%2==0)
			break;
	}
	while(1);
	check(n);
	return 0;
}