高考命题猜想一_高考猜题有猜中的吗

不明白的话加QQ群9209868,或QQ331012005

#include <iostream>

#include <cstdlib>

using namespace std;

const N = 10000;

typedef struct pair

{

int a;

int b;

}PAIR, *PPAIR;

void GetPrimeList(int* primelist, const int n);//将2到n的素数放到primelist里

int FindSum(int n, int* a, PPAIR result);//从a[1] 到a[a[0] -1] 中寻找是否有两个数的和等于n

int IsPrime(int n);//检查一个整数是不是素数

int CheckPrime(int* a);//将a[1]到a[a[0]-1]中不是素数的数列出来

int main()

{

int i;

int primelist[N/2];

PAIR result;

GetPrimeList(primelist, N);

if (CheckPrime(primelist) == 0)

for (i = 2; i < N + 1; i += 2)

{

if (FindSum(i, primelist, &result))

cout<<i<<"\t=\t"<<primelist[result.a]<<"\t+\t"\

<<primelist[result.b]<<endl;

else

cout<<i<<"\terror!"<<endl;

}

else

cout<<"prime list error!"<<endl;

system("pause");

return 0;

}

///////////////////////////////////////////////////////////////////////

//

// 函数名 : GetPrimeList

// 功能描述 : 将2到n的素数放到primelist里(筛选法)

// 从primelist[1]到primelist[primelist[0]-1]

// 参数 : int* primelist

// 参数 : const int n

// 返回值 : 空

//

///////////////////////////////////////////////////////////////////////

void GetPrimeList(int* primelist, const int n)

{

int* mark = new int[n+1];

int i, j;

for (i = 2; i < n + 1; i++)

{

mark[i] = 1;

}

for (i = 2; i < n + 1; )

{

for (j = i + 1; j < n + 1; j++)

if (j%i == 0)

mark[j] = 0;

while (++i < n + 1 && mark[i] == 0);

}

for (i = 2, j = 1; i < n + 1; i++)

if (mark[i])

primelist[j++] = i;

primelist[0] = j;

delete[] mark;

}

///////////////////////////////////////////////////////////////////////

//

// 函数名 : FindSum

// 功能描述 : 从a[1] 到a[a[0] -1] 中寻找是否有两个数的和等于n

// 参数 : int n

// 参数 : int* a

// 参数 : PPAIR result

// 返回值 : 找到返回1,结果在result中,否则返回0

//

///////////////////////////////////////////////////////////////////////

int FindSum(int n, int* a, PPAIR result)

{

int i, j;

result->a = result->b = 0;

for (i = 1; i < a[0] && a[i] < n; i++)

for (j = 1; j <= i; j++)

{

if (a[j] + a[i] < n)

continue;

if (a[j] + a[i] > n)

{

j = i + 1;

}

else

{

result->a = j;

result->b = i;

return 1;

}

}

return 0;

}

///////////////////////////////////////////////////////////////////////

//

// 函数名 : IsPrime

// 功能描述 : 检查一个整数是不是素数

// 参数 : int n

// 返回值 : 是素数返回1,否则返回0

//

///////////////////////////////////////////////////////////////////////

int IsPrime(int n)

{

int i;

if (n == 2) //排除n==2

return 1;

if (n%2 == 0 || n == 1) //排除n为偶数或1

return 0;

for (i = 3; i <= n/2 + 1; i += 2) // n/2+1可以换为sqrt(n)+1;注意#include <math.h>,有自动类型转换

if (n%i == 0) //所有的偶数都不是质数(排除了2),每循环一次i加2,比如4,6就不用考虑整除n了

return 0;

return 1;

}

///////////////////////////////////////////////////////////////////////

//

// 函数名 : CheckPrime

// 功能描述 : 将a[1]到a[a[0]-1]中不是素数的数列出来

// 参数 : int* a

// 返回值 : 不是素数的数的个数

//

///////////////////////////////////////////////////////////////////////

int CheckPrime(int* a)

{

int i;

int n = 0;

for (i = 1; i < a[0]; i++)

if (IsPrime(a[i]))

continue;

else

{

cout<<a[i]<<" is not a prime"<<endl;

n++;

}

return n;

}