嗯。想一下。
这个是分别以每个自然数为起点,开始遍历,结果会有重复。
比如
(1, 2, 3, 4, 7, 10, 9, 8, 5, 6)
(6, 1, 2, 3, 4, 7, 10, 9, 8, 5)
import java.util.ArrayListimport java.util.List
public class PrimeRing {
// 求1~n素数环
public PrimeRing(int n) {
List<Integer>src = new ArrayList<Integer>()
List<Integer>dest = new ArrayList<Integer>()
for (int i = 1i <= ni++) {
src.add(i)
}
loop(src, dest, n)
}
public void loop(List<Integer>src, List<Integer>dest, int n) {
if (dest.size() == n) {
Integer start = dest.get(0)
Integer end = dest.get(dest.size() - 1)
if (isPrime(start + end)) {
System.out.println(dest)
}
return
}
for (int i = 0i <src.size()i++) {
Integer element = src.remove(i)
if (dest.isEmpty()) {
dest.add(element)
} else {
Integer tmp = dest.get(dest.size() - 1)
if (isPrime(tmp + element)) {
dest.add(element)
} else {
src.add(i, element)
continue
}
}
loop(src, dest, n)
src.add(i, element)
dest.remove(dest.size() - 1)
}
}
// 判断k是否为素数
public boolean isPrime(int k) {
if (k == 2)
return true
if (k <2 || k >2 &&k % 2 == 0)
return false
int j = (int) Math.sqrt(k)// Math.sqrt(k)返回k的平方根值
if (j % 2 == 0)
j--// 获得测试范围内的最大奇数
while (j >2 &&k % j != 0)
j -= 2
return j <2
}
public static void main(String args[]) {
new PrimeRing(10)
}
}
素数环是一个计算机程序问题,指的是将从1到n这n个整数围成一个圆环,若其中任意2个相邻的数字相加,结果均为素数,那么这个环就成为素数环。其中程序方面包括递归实现(C语言)和递归实现(C++),以及递归实现(Pascal)、非递归实现(Java)、回溯实现(php)等多种方法。