primering1.cpp

是一本教程的实例代码,可以下载后直接运行,即可以得到答案.

typedef int dataType;                  //抽象数据类型dataType定义为int
#include "Queue1.h"                    //顺序循环队列类

bool isPrime(int k)                    //判断k是否为素数
{
    int j=2;
    if(k==2)
        return true;
    if(k<2 || k>2 && k%2==0)
        return false;
    else        
    {
        j=3;
        while(j<k && k%j!=0)
            j=j+2;
        if(j>=k)
            return true;
        else  
            return false;
    }
}

void output(int a[],int n)             //输出数组元素值
{
    for(int i=0;i<n;i++)
        cout<<a[i]<<"  ";
    cout<<"\n";
}

void primering(int n)                  //求1~n素数环
{
    int i,j,k;
    Queue1 q1(20);                     //创建一个空队列，存储单元个数为20 
    int *ring1=new int [n];            //申请一个数组表示素数环
    ring1[0]=1;                        //1添加到素数环中
    for (i=2;i<=n;i++)                 //2~n全部入队
        q1.enQueue(i);
    cout<<"队列: "<<q1;                //输出队列中各数据元素值
    i=0;
    while(!q1.isEmpty()) 
    {
        k=q1.deQueue();                //出队
        cout<<"deQueue: "<<k<<"\t";
        j=ring1[i]+k;
        if(isPrime(j))                 //判断j是否为素数
        {
            i++;
            ring1[i]=k;                //k添加到素数环中
        }
        else
            q1.enQueue(k);             //k再次入队
        cout<<"队列: "<<q1;
    }
    output(ring1,n);                   //输出队列中各数据元素值
}

void main()
{
    primering(10);
}

/*
程序运行结果如下：
队列: 2 3 4 5 6 7 8 9 10 
deQueue: 2	队列: 3 4 5 6 7 8 9 10 
deQueue: 3	队列: 4 5 6 7 8 9 10 
deQueue: 4	队列: 5 6 7 8 9 10 
deQueue: 5	队列: 6 7 8 9 10 5 
deQueue: 6	队列: 7 8 9 10 5 6 
deQueue: 7	队列: 8 9 10 5 6 
deQueue: 8	队列: 9 10 5 6 8 
deQueue: 9	队列: 10 5 6 8 9 
deQueue: 10	队列: 5 6 8 9 
deQueue: 5	队列: 6 8 9 5 
deQueue: 6	队列: 8 9 5 6 
deQueue: 8	队列: 9 5 6 8 
deQueue: 9	队列: 5 6 8 
deQueue: 5	队列: 6 8 5 
deQueue: 6	队列: 8 5 6 
deQueue: 8	队列: 5 6 
deQueue: 5	队列: 6 
deQueue: 6	队列: 
1  2  3  4  7  10  9  8  5  6  
*/