队列应用-素数环问题

问题描述： 将从1到n这n个整数围成一个圆环，若其中任意2个相邻的数字相加，结果均为素数，那么这个环就成为素数环。

求解思路：

先将1放入素数环，设置一个队列，将2-n的自然数全部入队，每次对出对的一个元素k进行测试，若符合要求，则将k加入到素数环中，否则将k再次入队等待，重复次不步骤直至队列为空。

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 素数环问题 
 *
 */
public class PrimeRing {
    //求1-n素数环
    public PrimeRing(int n){
        List<Integer> ring=new ArrayList<Integer>();//用于存储素数环
        ring.add(1);    //将1添加到素数环中
        Deque<Integer> que=new ArrayDeque<Integer>(n); //创建一个队列,FIFO

        //2-n全部入队
        for(int i=2;i<=n;i++){
            que.addLast(i); //依次入队
        }

        int i=0;
        while(!que.isEmpty()){
            int k=que.removeFirst(); //队首元素出队
            if(isPrime(ring.get(i)+k)){
                i++;
                ring.add(k);
            }else{
                que.addLast(k);
            }
        }
        System.out.println("素数环："+ring.toString());
    }


    //判断一个数是否为素数
    public boolean isPrime(int n){
        if(n==2)
            return true;
        if(n<2 || n>2 && n%2==0)
            return false;
        int j=(int)Math.sqrt(n); //返回n的平方根
        if(j%2==0)
            j--;
        while(j>2 && n%j!=0)
            j-=2;
        return j<2;
    }

    public static void main(String[] args) {
        PrimeRing pr=new PrimeRing(10);
    }
}