問題描述：將從1到n這n個整數(shù)圍成一個圓環(huán)，若其中任意2個相鄰的數(shù)字相加，結(jié)果均為素數(shù)，那么這個環(huán)就成為素數(shù)環(huán)。

n=20時，下面的序列就是一個素數(shù)環(huán)：

1?2?3?4?7?6?5?8?9?10?13?16?15?14?17?20?11?12?19?18

下面的程序利用回溯法窮舉所有可能性，試圖找到一個解。既然是環(huán)，第一個位置可以隨意取一個數(shù)值(好象設(shè)置為1比其它數(shù)計算起來都要快，不信你把程序中的

ring[0] 設(shè)置為18計算一下。另外n好象只是偶數(shù)的時候才存在素數(shù)環(huán))。這個問題應(yīng)該還有很多種解法，和遞歸、圖的 DFS

搜索、哈密頓環(huán)都有關(guān)系。我的問題是，能否寫出一個比較高效的算法計算出對于任意n的全部素數(shù)環(huán)序列？

#include

#include

#define LEN 20

int primeRing(int ring[], int b[], int n);

int isPrime(int n);

int main(void)

{

int i, ring[LEN]={0}, b[LEN]={0};

ring[0] = 1;

b[0] = 1;

if( primeRing(ring, b, 1) )

{

printf("\n\nThe prime ring is :

");

for(i=0; i

i++)

printf("%d ",

ring[i]);

printf("\n");

}

else

printf("\n\nNot found!\n");

return 0;

}

int primeRing(int ring[], int b[], int n)

{

int i;

if( n==LEN )

return

isPrime(ring[n-1]+ring[0]);

printf("\nCalculating ring[%d] = ", n);

for(i=1; i

if( b[i]==0

&& isPrime((i+1)+ring[n-1]) )

{

b[i] =

1;

ring[n] =

i+1;

printf("%d ",

ring[n]);

if(

primeRing(ring, b, n+1) )

return

1;

else

b[i]

= 0;

}

return 0;

}

int isPrime(int n)

{

int i, t, f=1;

t = sqrt(n);

for(i=2; i<=t; i++)

if( n%i==0 )

{

f = 0;

break;

}

return f;

}

與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的质数环问题c语言,素数环问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。