java求解素数环问题（java 求素数）

本文目录一览：

• 1、数据结构求解素数环问题（JAVA版）：将N个自然数（1~N），使得每相邻两数之和为素数，构成一个素数环！
• 2、悬赏并跪求C语言大神帮忙解决此问题！关于素数环的
• 3、C语言素数环问题：输入n，输出n以内的素数环。我感觉思路是对的，怎么没有输出，请大侠看看！
• 4、回溯法求解素数环问题的时间复杂度分析
• 5、Exception in thread “main” java.lang.NumberFormatException:

数据结构求解素数环问题（JAVA版）：将N个自然数（1~N），使得每相邻两数之和为素数，构成一个素数环！

嗯。想一下。

这个是分别以每个自然数为起点，开始遍历，结果会有重复。

比如

(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) {

ListInteger src = new ArrayListInteger();

ListInteger dest = new ArrayListInteger();

for (int i = 1; i = n; i++) {

src.add(i);

}

loop(src, dest, n);

}

public void loop(ListInteger src, ListInteger 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);

}

}

悬赏并跪求C语言大神帮忙解决此问题！关于素数环的

文件输入输出应该不用多说吧。

freopen(“prime.in”,”r”,stdin);

freopen(“prime.out”,”w”,stdout);

至于算法的话，就是暴力搜索加剪枝：

如果当前值与上一个值之和是一个素数才继续向下搜索

用一个stack[N]记录数字

深搜过程：

void dfs(int depth)

{

if (depthn)

{

if (judge(stack[1]+stack[n]))

{

for (int i=1;i=n;++i)

printf(“%d “,stack[i]);

printf(“\n”);

}

return ;

}

for (int i=1;i=n;i++)

if (!flag[i] judge(stack[depth-1]+i))

{

stack[depth]=i;

flag[i]=1;

dfs(depth+1);

flag[i]=0;

}

}

判断素数

bool judge(int N) //返回0为不是素数，返回1为是素数

{

if (N2) return 0;

for (int i=2;i=(int)sqrt(N);++i)

if (N%i) return 0;

return 1;

}

最后注意一点，在执行dfs过程时直接dfs(2)，然后令stack[1]=1;因为当stack[1]1之时，它的解可以由stack[1]=1时的解变换而来。flag[i]是记录该数出现过没有，因为每个数只能出现一次。

C语言素数环问题：输入n，输出n以内的素数环。我感觉思路是对的，怎么没有输出，请大侠看看！

#includestdio.h

#includestring.h

int is_prime(int x)

{

int i,flag;

for(i=2;i=x/2;i++)

if(x%i==0)

return 0;

return 1;

}

void dfs(int n,int *a,int *isp,int *vis,int cur)

{

if(cur==nisp[a[0]+a[n-1]])

{

for(int i=0;in;i++)

printf(“%d “,a[i]);

printf(“\n”);

return ;

}

else

for(int i=1;i=n;i++)

if(!vis[i]isp[i+a[cur-1]])//如果i没有用过，并且与前一个数之和为素数

{

a[cur]=i;

vis[i]=1;

dfs(n,a,isp,vis,cur+1);

vis[i]=0;

}

}

int main()

{ int i,n,a[100],isp[100],vis[100];

memset(vis,0,sizeof(vis));

memset(isp,0,sizeof(isp));

scanf(“%d”,n);

for(i=0;in;i++)

a[i]=i+1;

for(i=1;i100;i++)

isp[i]=is_prime(i);

dfs(n,a,isp,vis,0);

return 0;

}

判断素数有问题

回溯法求解素数环问题的时间复杂度分析

其时间复杂度应该是O(!n)因为需要找到满足素数环的所有条件的取值，等价于找到2～n的其中一个排列。

C++的回溯素数环：

#includeiostream

using namespace std;

int n;

int a[20];

bool vist[20];

bool isPrime(int x){

if(x  2) return false;

for(int i = 2; i*i = x; i++){

if(x%i == 0) return false;

}

return true;

}

void print(){

for(int i = 0; i = n-1; i++){

cout  a[i]  ” “;

}

cout  endl;

}

void dfs(int cur){

int i;

if(cur == n  isPrime(a[n-1]+a[0])){

print();

return;

}

for(i = 2; i = n; i++){

if(!vist[i]isPrime(i+a[cur-1])){

a[cur] = i;

vist[i] = 1;

dfs(cur+1);

vist[i] = 0;

}

}

}

int main(){

cin  n;

if(n%2 == 0){

a[0] = 1;

vist[1] = 1;

dfs(1);

} 

return 0;

}

Exception in thread “main” java.lang.NumberFormatException:

printf 格式化输出

%d 是数值

而根据报告的错误 数值转换异常

基本上可以认定 是非数值字符串转换成数值造成的