Go语言视频零基础入门到精通

javalearner

关于素数环问题，我在早先的一个帖子里已经做了详细的说明。那时候我用的是递归的方式来实现的。今天我又使用非递归的方式把这个问题做了一遍，有兴趣的网友可以一起探讨！

1. public class Main {
   
2.     public static void main(String[] args) {
   
3.         primering(20);
   
4.     }
   
5.     public static void primering(int n) {
   
6.         if(n % 2 != 0) {
   
7.             System.out.println("若要实现素数环，元素的个数必须为偶数，您的输入不符合要求！");
   
8.             return;
   
9.         }
   
10.         
    
11.         int[] a = new int[n];
    
12.         a[0] = 1;
    
13.         int i = 1;
    
14.         boolean flag = true; // true表示正常向下一级移动，false表示回溯到上一级
    
15.         int first;
    
16.         while (i < n) {
    
17.             //选择一个元素
    
18.             //如果是正常向下一级移动，该元素应该是当前未使用的最小的数
    
19.             //若是从下一层回溯上来的，则该元素为“比当前值大的，并且未被使用的，最小的一个数”
    
20.             for1: for (a[i] = flag ? 2 : a[i] + 1; a[i] <= n; a[i]++) {
    
21.                 for (int j = 0; j < i; j++) {//检验选择的元素是否曾经用过
    
22.                     if (a[i] == a[j])
    
23.                         continue for1;
    
24.                 }
    
25.                 break;
    
26.             }
    
27.         //若选择的元素超过了最大值，则应该回溯
    
28.             if (a[i] > n) {
    
29.                 i--;
    
30.                 flag = false;
    
31.                 continue;
    
32.             }
    
33.             // 如果当前找到的元素与前一个元素的和是素数
    
34.             if (isPrime(a[i] + a[i - 1])) {
    
35.                 if (i < n - 1) { // 如果不是最后一个元素，则向下一级寻找
    
36.                     i++;
    
37.                     flag = true;
    
38.                 } else if (isPrime(a[i] + a[0])) { // 如果是最后一个元素并且于环的第一个元素的和仍然是素数
    
39.                     break;        //则素数环已经找到，退出循环
    
40.                 } else {    //若是最后一个元素，并且不满足素数环
    
41.                     i--;    //则向上一级回溯
    
42.                     flag = false;
    
43.                 }
    
44.             } else {    //若当前元素不满足素数环，则继续寻找
    
45.                 flag = false;
    
46.             }
    
47.         }
    
48.         
    
49.         //打印素数环
    
50.         for(int x:a) {
    
51.             System.out.print(x+"  ");
    
52.         }
    
53.     }
    
54.     public static boolean isPrime(int n) {
    
55.         int i;
    
56.         for (i = 2; i < n; i++)
    
57.             if (n % i == 0)
    
58.                 break;
    
59.         return i==n;
    
60.     }
    
61. }

复制代码

运行结果： C:        est>java Main
1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 20 11 12 19 18

源码下载：http://file.javaxxz.com/2014/11/6/000318046.zip