goldbach.cpp

问题描述： 哥德巴赫猜想：任何大偶数均可表示为2 个素数之和。

#include<iostream.h>
#include<fstream.h>
#include<math.h>
struct  node { //素数判定表中的结点定义
 int  isPrime; //isPrime取1表示该元素是素数,取0表示该元素不是素数
 int  next; //next指向下一个素数所在下标
};
class NumberLink;

class  NumberNode { //存放初始读入数据的链结点定义
 friend  void  main();
 friend  NumberLink;
 private:
   int number;  //链结点中存放的数据
   NumberNode  *next;  //链结点中的后继指针域
};
class  NumberLink {
 friend  void  main();
 private:
 	NumberNode *first,*rear; //链表的头指针和尾指针
 public:
	 NumberLink() { first=rear=0; }
	 ~NumberLink() { //在析构函数中释放链表中所有结点的空间
		NumberNode  *p;
		while (first) {
		  p=first->next;
		  delete first;
		  first=p;		  
		}
		rear=0;
	 }
	 void  InsertRear(int x) { //在链表尾部插入一个新结点
        NumberNode  *p=new NumberNode;
		p->number=x;
		p->next=0;
		if (rear)  rear->next=p;
		else  first=p;
		rear=p;
	 }
};

void main() {
 ifstream  in("input.txt");
 ofstream  out("output.txt");
 NumberLink  nlink;
 int  max=0;
 int x;
 while (1) { //将各输入数据读入链表中,每次在链表尾部插入,并将最大元素保存在max中
	in>>x;
	if (x==0)  break;
	if (x>max)  max=x;
	nlink.InsertRear(x);
	}

 node  *table=new  node[max+1]; //为素数判定表分配空间
 table[0].isPrime=table[1].isPrime=0; //0和1一定不是素数
 for (int i=2; i<=max; i++) 
	table[i].isPrime=1; //将2~max初始化为素数
 int  prev=2;
 for ( i=2; i<=sqrt(max); i++) {
	 if (table[i].isPrime==1) { 
	  for (int j=2; j*i<=max;  j++) //将所有是素数i的整数倍的数设置为非素数
		table[j*i].isPrime=0;
	  if (i!=2) { table[prev].next=i; //将判定表中的当前素数链接至一个静态链表中
	   prev=i;
	  }
	 }
 }
 for (; i<=max; i++) { //将判定表中剩余素数链接至静态链表
	 if (table[i].isPrime==1 && i!=2) {
		 table[prev].next=i;
		 prev=i;
	 } 
 }
 table[prev].next=-1; //设置静态链表中最后一个结点的指针域
 
 
 NumberNode  *p=nlink.first;
 for (; p; p=p->next) { //对输入数据链表中的每个输入数据进行处理
	 int  num=0;
	 
	for (int i=2; i<=(p->number)/2; i=table[i].next) 
		//对输入数据n,考察2~n/2中每个素数i是否能使n-i为素数,若能则n能表示成的素数对数目加1
        if  (table[(p->number-i)].isPrime==1)
		  num++;
	 out<<num<<endl;
 }

 delete []table;
 }