关键词：
//【例4.3】 求解素数环问题。
public class PrimeRing
public PrimeRing(int n) //求1～n素数环
SeqList<Integer> ring = new SeqList<Integer>(n); //创建一个顺序表存储素数环
ring.append(new Integer(1)); //1添加到素数环中
SeqQueue<Integer> que = new SeqQueue<Integer>(n); //创建一个队列que// LinkedQueue<Integer> que = new LinkedQueue<Integer>(); //创建一个队列que
for (int i=2; i<=n; i++) //2～n全部入队
que.enqueue(new Integer(i));
// System.out.println(que.toString());
int i=0;
while (!que.isEmpty())
int k = que.dequeue().intValue(); //出队
// System.out.print("dequeue: "+k+"\t");
if (isPrime(ring.get(i)+k)) //判断是否为素数
i++;
ring.append(new Integer(k)); //k添加到素数环中
else
que.enqueue(new Integer(k)); //k再次入队
// System.out.println("队列: "+que.toString());
System.out.println("素数环: "+ring.toString());
public boolean isPrime(int k) //判断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, 2, 3, 4, 7, 10, 9, 8, 5, 6)
问题：上述的算法不完全，并且未求多个解，求完整（求多个解）算法！（N为10)
嗯。想一下。
这个是分别以每个自然数为起点，开始遍历，结果会有重复。
比如
(1, 2, 3, 4, 7, 10, 9, 8, 5, 6)
(6, 1, 2, 3, 4, 7, 10, 9, 8, 5)
import java.util.ArrayList;
import 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 = 1; i <= n; i++)
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 = 0; i < 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);
我运行了一下你的算法，能够得出所有解，但是我的题目是素数环，也就是首个数字和尾数字的和也应该要判断是否为素数。还有就是可以完善一下我上面那个用队列的算法么，麻烦啦，好的话可以给你分。
追答你上面那个是一个解的算法，要完善什么？
我得到结果有，有首和尾，相加不是素数的吗？
if (isPrime(start + end))
System.out.println(dest);
这个地方有判断啊，应该是没有错啊。
噢噢，看到了哈哈。你的算法挺好的，但是因为我这是java数据结构的课程设计，题目是完善我上面的算法，就是上面的算法的结果只有一个解，要完善的有：1.判断首尾两数之和为素数；2.给定初始序列，求多个解。 麻烦啦。
追答SeqList
SeqQueue
这两个类是什么？我就是找不到这两个类，才换了一下，
基本和你那个差不多，判断素数的方法也没有变。
这两个类 Seqlist 是顺序表类（线性表LList类的子类） SeqQueue顺序循环队列类（对列Queue的子类） 我可以发那几个类的声明给你的。
追答嗯，好，你把这两个类发给我，这个应该是你自己实现的，我找不到这两个类。
参考技术A 那就加上第一个元素和最后一个元素的判断就是！这还不全，把能写的都写出来了。这是什么书啊，求推荐啊！ 参考技术B 纯算法，最讨厌算法的了。。。。素数环
...成一个圆环，若其中任意2个相邻的数字相加，结果均为素数，那么这个环就成为素数环。 n=20时，下面的序列就是一个素数环： 1234765891013161514172011121918 php版本回溯算法：1<?php2//素数环问题3include"show.php";45define("LEN"... 查看详情
codevs1031质数环
一个大小为N(N<=17)的质数环是由1到N共N个自然数组成的一个数环，数环上每两个相邻的数字之和为质数。如下图是一个大小为6的质数环。为了方便描述，规定数环上的第一个数字总是1。如下图可用143256来描述。若两个质数环... 查看详情
回溯1--素数环
回溯2--素数环一、心得 二、题目及分析素数环是一个计算机程序问题，指的是将从1到n这n个整数围成一个圆环，若其中任意2个相邻的数字相加，结果均为素数，那么这个环就成为素数环。计算1-20这20个数形成的素数环.三、... 查看详情
求解第n个素数
...素数，却把前N个素数都求了出来，那有没有一个直接能求解第N个素数是什么的方法呢？答案当然是。。。没有。但是，有一种方法用迭代的方法能够求解π（x），即是0~x中素数的个数，它就是梅塞尔—勒梅尔公式，黑科技... 查看详情
求解大于某数的下一个素数
求解大于某数的下一个素数问题，常见于求某一范围内的所有素数，第k个素数问题中，由于素数一定是奇数，而两个相邻奇数之间一定相差2，所以只要在奇数中查找即可：代码如下intNextPrime(intN){if(N%2==0)++N;inti;boolNotPrime=false;for(... 查看详情
nyoj488素数环
素数环时间限制：1000 ms | 内存限制：65535 KB难度：2描述有一个整数n，把从1到n的数字无重复的排列成环，且使每相邻两个数（包括首尾）的和都为素数，称为素数环。为了简便起见，我们规定每个素数环都从1开... 查看详情
hdu1016素数环---（dfs）
http://acm.hdu.edu.cn/showproblem.php?pid=1016SampleInput68 SampleOutputCase1:143256165234Case2:12385674125834761476583216743852题意：输入整数n (0<n<20).找出n个整数，能组成一个环，环中任意相邻两数之和为素数，字典序输出所有情况, 查看详情
递归-约瑟夫环(代码片段)
...=10,m=17输出: 2限制：1<=n <=10^51<=m<=10^6问题求解：使用递归求解可以在O(n)的时间复杂度求解。时间复杂度：O(n)publicintlastRemaining(intn,intm)if(n==1)return0;return(lastRemaining(n-1,m)+m)%n; 查看详情
dfs素数环问题(代码片段)
...输入正整数n，对1-n进行排列，使得相邻两个数之和均为素数，输出时从整数1开始，逆时针排列。同一个环应恰好输出一次。n<=16 如输入：6 输出：143256165234代码： 1importjava.util.Scanner;23publicclass素数环45publicstaticvoidmain(... 查看详情
p1186反素数（模板题）
描述Description如果一个自然数比所有比它小的自然数的约数个数都要多，那么我们就称这个数为一个反素数。例如，1、2、4、6、12和24都是反素数。任务：请写一个程序：○读入一个自然数n;○找出不大于n的最大的反素... 查看详情
nyoj488
素数环时间限制：1000 ms | 内存限制：65535 KB难度：2 描述有一个整数n，把从1到n的数字无重复的排列成环，且使每相邻两个数（包括首尾）的和都为素数，称为素数环。为了简便起见，我们规定每个素数环... 查看详情
pat乙级1013(代码片段)
...无穷第m到n个素数//质数又称素数。指整数在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。//换句话说，只有两个正因数（1和 查看详情
Python半素数分解方程求解器问题
】Python半素数分解方程求解器问题【英文标题】：Pythonsemiprimefactorizationequationsolverissues【发布时间】：2012-02-1914:43:35【问题描述】：我是一名农民/新手数论研究员。几年前，我碰巧发现了一种出现在素数分布中的模式，该模式... 查看详情
uva-524primeringproblem（素数环）（回溯法）
题意：输入n，把1~n组成个环，相邻两个数之和为素数。分析：回溯法。#pragmacomment(linker,"/STACK:102400000,102400000")#include<cstdio>#include<cstring>#include<cstdlib>#include<cctype>#include<cmath>#inc 查看详情
约瑟夫环问题，一道经典的数据结构题目
问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。一般我们采用一个循环队列来模拟约瑟夫环的求解过程，但是如果n比较大的时候，采用模拟的方式求解，需要大量的... 查看详情
梦工场实验室素数求和神奇的素数筛选
...sp; 解决: 30[提交][状态][讨论版]题目描述输入一个自然数n，求小于等于n的素数之和输入 输出 样例输入2样例输出2提示测试样例保证 2<=n<=2,000,000 &nbs 查看详情
1031质数环
...描述Description一个大小为N(N<=17)的质数环是由1到N共N个自然数组成的一个数环，数环上每两个相邻的数字之和为质数。如下图是一个大小为6的质数环。为了方便描述，规定数环上的第一个数字总是1。如下图可用143256来描述。若... 查看详情
10000以内质数的分布规律是啥？
...术A10000以内的质数如下图：质数又称素数。一个大于1的自然数，除了1和它自身外，不能整除其他自然数的数叫做质数；否则称为合数。1、如果为合数，因为任何一个合数都可以分解为几个素数的积。2、其他数学家给出了一些... 查看详情