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 是數值

而根據報告的錯誤 數值轉換異常

基本上可以認定 是非數值字元串轉換成數值造成的