/*
作者:ZouV
时间:2010年12月06日
功能:
输出 "1-输入值" 区间内的所有素数
*/
#include <iostream>
#include <iomanip>
#include <conio.h>
using namespace std;
//定义存储素数的缓存,定义为顺序表结构
struct SSqeList
{
int *point;
int length;
int size;
};
//找出并保存所有素数,该函数的返回值为SSqeList结构体类型
SSqeList FindPrimeNumber(int maxNumber);
void main()
{
SSqeList slist;
slist=FindPrimeNumber(523); //??? 为什么最大只能是523?
for(int i=0;i<slist.length;i++)
{
cout<<setw(5)<<*(slist.point+i)<<" ";
if(i%10==0)
cout<<endl;
}
getch();
}
SSqeList FindPrimeNumber(int maxNumber)
{
SSqeList slist;
int *p;
int time; //累计给缓存分配内存的次数
int memLength=100; //每次分配给缓存的内存空间的大小
//初始化
time=1;
slist.length=0;
slist.size=memLength;
slist.point=(int*)malloc(slist.size * sizeof(int));
//判断查找区间是否合法
if(maxNumber<=0)
{
cout<<"输入的查找区间不合法!"<<endl;
return slist;
}
//加入第一个素数
*(slist.point + slist.length)=1;
slist.length++;
if(maxNumber==1)
return slist;
//加入第二个素数
*(slist.point + slist.length)=2;
slist.length++;
if(maxNumber==2)
return slist;
for(int i=3;i<=maxNumber;i++)
{
//缓存不够,分配空间
if(slist.length==slist.size)
{
time++;
p=(int*)malloc(memLength*time*sizeof(int));
memcpy(p,slist.point,memLength*sizeof(int));
slist.size=time*memLength;
slist.point=(int*)malloc(sizeof(memLength*time*sizeof(int)));
memcpy(slist.point,p,memLength*sizeof(int));
}
//查找素数
for(int j=1;j<slist.length;j++)
{
if(i % *(slist.point+j) == 0) //满足此条件为合数
{
break;
}
if(j==slist.length-1)
{
*(slist.point+slist.length)=i; //为素数就存入缓存中
slist.length++;
}
}
}
return slist;
}