关于素数环问题,我在早先的一个帖子里已经做了详细的说明。那时候我用的是递归的方式来实现的。今天我又使用非递归的方式把这个问题做了一遍,有兴趣的网友可以一起探讨!
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiIml2ZuUmbv50LcNncvRXYjlGZul0ZulmbpxGd190LcdmbpRHanlGbodWaohXY05Wez9CX0Vmbu4GZzNmLzV2Zh1Wavw1LcpDc0RHaiojIsJye.gif)
package andycpp;
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiIml2ZuUmbv50LcNncvRXYjlGZul0ZulmbpxGd190LcdmbpRHanlGbodWaohXY05Wez9CX0Vmbu4GZzNmLzV2Zh1Wavw1LcpDc0RHaiojIsJye.gif)
public class Main ...{
public static void main(String[] args) ...{
primering(20);
}
public static void primering(int n) ...{
if(n % 2 != 0) ...{
System.out.println("若要实现素数环,元素的个数必须为偶数,您的输入不符合要求!");
return;
}
int[] a = new int[n];
a[0] = 1;
int i = 1;
boolean flag = true; // true表示正常向下一级移动,false表示回溯到上一级
int first;
while (i < n) ...{
//选择一个元素
//如果是正常向下一级移动,该元素应该是当前未使用的最小的数
//若是从下一层回溯上来的,则该元素为“比当前值大的,并且未被使用的,最小的一个数”
for1: for (a[i] = flag ? 2 : a[i] + 1; a[i] <= n; a[i]++) ...{
for (int j = 0; j < i; j++) ...{//检验选择的元素是否曾经用过
if (a[i] == a[j])
continue for1;
}
break;
}
//若选择的元素超过了最大值,则应该回溯
if (a[i] > n) ...{
i--;
flag = false;
continue;
}
// 如果当前找到的元素与前一个元素的和是素数
if (isPrime(a[i] + a[i - 1])) ...{
if (i < n - 1) ...{ // 如果不是最后一个元素,则向下一级寻找
i++;
flag = true;
} else if (isPrime(a[i] + a[0])) ...{ // 如果是最后一个元素并且于环的第一个元素的和仍然是素数
break; //则素数环已经找到,退出循环
} else ...{ //若是最后一个元素,并且不满足素数环
i--; //则向上一级回溯
flag = false;
}
} else ...{ //若当前元素不满足素数环,则继续寻找
flag = false;
}
}
//打印素数环
for(int x:a) ...{
System.out.print(x+" ");
}
}
public static boolean isPrime(int n) ...{
int i;
for (i = 2; i < n; i++)
if (n % i == 0)
break;
return i==n;
}
}
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiIml2ZuUmbv50LcNncvRXYjlGZul0ZulmbpxGd190LcdmbpRHanlGbodWaohXY05Wez9CX0Vmbu4GZzNmLzV2Zh1Wavw1LcpDc0RHaiojIsJye.gif)