网上有很多关于埃拉托色尼筛选法的实现但没有利用链表的，下面是我写的程序
#include
#include
#include
using namespace std;
class prime
{
public:
struct list//可以建立有last的链表但会多占用50%内存
{
int number;
list *Next;
};
void showList(list*first)
{
cout<<"List:\n"<number<<"\t";
while(first->Next!=NULL)
{
cout<Next->number<<"\t";
first->Next=first->Next->Next;
}
cout<<"\nOVER By Steven Grove\n";
}
list*MakeList(int left,int right)//建立链表（需要1<=Left<=right)
{
if(left<=right&&left>=1)
{
struct list* first=new list;
struct list* temp=first;
for(int i=left;i
{
temp->number=i;
temp->Next=new list;
temp=temp->Next;
}
temp->Next=NULL;
temp->number=right;
return first;
}
else
{
return NULL;
}
}
list*isPrime(list*first)
{
list*tempList=first->Next;//用于保存每一次中临时list
list*tempFirst=first->Next;//用来保存每一次的最小数
while(1)
{
if (tempFirst->Next!=NULL)//判断是否读取到最后一个（否：结束）
{
if(tempList==NULL||tempList->Next==NULL)//判断一次是否结束（是：结束）
{
tempFirst=tempFirst->Next;//下一次，最小数重新赋值
tempList=tempFirst;
}
else
{
if(tempList->Next->number%tempFirst->number==0)//判断是否为最小数的倍数
{
tempList->Next=tempList->Next->Next;
}
tempList=tempList->Next;
}
}
else
break;
}
return first;
}
};
int _tmain(int argc, _TCHAR* argv[])
{
cout<<"Press the max larger than 1 :\t";
int max;
scanf_s("%d",&max);
prime pi;
prime::list*first=pi.MakeList(1,max);
prime::list*result=pi.isPrime(first);
pi.showList(first);
_getwche();
return 0;
}
阅读(413) | 评论(0) | 转发(0) |
