【正文】 r it39。s square(palindrome)1 1 12 2 43 3 94 11 1215 22 4846 26 6767 101 102018 111 123219 121 14641=(ab+cd)2性質(zhì)的四位數(shù)3025這個數(shù)具有一種獨(dú)特的性質(zhì)：將它平分為二段，即30和25，使之相加后求平方，即(30+25)2，恰好等于3025本身。請求出具有這樣性質(zhì)的全部四位數(shù)。*問題分析與算法設(shè)計具有這種性質(zhì)的四位數(shù)沒有分布規(guī)律，可以采用窮舉法，對所有四位數(shù)進(jìn)行判斷，從而篩選出符合這種性質(zhì)的四位數(shù)。具體算法實現(xiàn)，可任取一個四位數(shù)，將其截為兩部分，前兩位為a，后兩位為b，然后套用公式計算并判斷。*程序說明與注釋includeint main(){int n,a,b。printf(There are following number with 4 digits satisfied condition\n)。for(n=1000。n10000。n++) /*四位數(shù)N的取值范圍1000~9999*/{a=n/100。 /*截取N的前兩位數(shù)存于a*/b=n%100。 /*截取N的后兩位存于b*/if((a+b)*(a+b)==n) /*判斷N是否為符合題目所規(guī)定的性質(zhì)的四位數(shù)*/printf(%d ,n)。}}*運(yùn)行結(jié)果There are following numbers with 4 digits satisfied condition:2025 3025 9801 求素數(shù)表中1~1000之間的所有素數(shù)*問題分析與算法設(shè)計素數(shù)就是僅能衩1和它自身整除的整數(shù)。判定一個整數(shù)n是否為素數(shù)就是要判定整數(shù)n能否被除1和它自身之外的任意整數(shù)整除，若都不能整除，則n為素數(shù)。程序設(shè)計時i可以從2開始，到該整數(shù)n的1/2為止，用i依次去除需要判定的整數(shù)，只要存在可以整除該數(shù)的情況，即可確定要判斷的整數(shù)不是素數(shù)，否則是素數(shù)。*程序說明與注釋includeint main(){int n1,nm,i,j,flag,count=0。do{printf(Input START and END=?)。scanf(%d%d,amp。n1,amp。nm)。 /*輸入求素數(shù)的范圍*/}while(!(n10amp。amp。n1nm))。 /*輸入正確的范圍*/printf(………..PRIME TABLE(%d–%d)…………\n,n1,nm)。if(n1==1||n1==2) /*處理素數(shù)2*/{printf(%4d,2)。n1=3。count++。}for(i=n1。i=nm。i++) /*判定指定范圍內(nèi)的整數(shù)是否為素數(shù)*/{if(!(i%2))continue。for(flag=1,j=3。flagamp。amp。ji/2。j+=2)/*判定能否被從3到整數(shù)的一半中的某一數(shù)所整除*/if(!(i%j))flag=0。 /*若能整除則不是素數(shù)*/if(flag) printf(++count%15?%4d:%4d\n,i)。}}*思考題請找出十個最小的連續(xù)自然數(shù)，它們個個都是合數(shù)(非素數(shù)) C/C++語言經(jīng)典、實用、趣味程序設(shè)計編程百例精解（4）驗證：2000以內(nèi)的正偶數(shù)都能夠分解為兩個素數(shù)之和(即驗證歌德巴赫猜想對2000以內(nèi)的正偶數(shù)成立)。*問題分析與算法設(shè)計為了驗證歌德巴赫猜想對2000以內(nèi)的正偶數(shù)都是成立的，要將整數(shù)分解為兩部分，然后判斷出分解出的兩個整數(shù)是否均為素數(shù)。若是，則滿足題意；否則重新進(jìn)行分解和判斷。程序中對判斷是否為素數(shù)的算法進(jìn)行了改進(jìn)，對整數(shù)判斷“用從2開始到該整數(shù)的一半”改為“2開始到該整數(shù)的平方根”。原因何在請自行分析。*程序說明與注釋includeincludeint fflag(int n)。int main(){int i,n。for(i=4。i=2000。i+=2){for(n=2。ni。n++) /*將偶數(shù)i分解為兩個整數(shù)*/if(fflag(n)) /*分別判斷兩個整數(shù)是否均為素數(shù)*/if(fflag(in)){printf(%14d=%d+%d\n,i,n,in)。 /*若均是素數(shù)則輸出*/break。}if(n==i) printf(error %d\n,i)。}}int fflag(int i) /*判斷是否為素數(shù)*/{int j。if(i=1)return 0。if(i==2)return 1。if(!(i%2))return 0。 /*if no,return 0*/for(j=3。j=(int)(sqrt((double)i)+1)。j+=2)if(!(i%j))return 0。return 1。 /*if yes,return 1*/} 求四位的可逆素數(shù)?？赡嫠財?shù)指：一個素數(shù)將其各位數(shù)字的順序倒過來構(gòu)成的反序數(shù)也是素數(shù)。*問題分析與算法設(shè)計　　本題的重點不是判斷素數(shù)的方法，而是求一個整數(shù)的反序數(shù)。求反序數(shù)的方法是從整數(shù)的末尾依次截取最后一位數(shù)字，每截取一次后整數(shù)縮小10倍，將截取的數(shù)字作為新的整數(shù)的最后一位（新的整數(shù)擴(kuò)大10倍后加上被截取的數(shù)字）。這樣原來的整數(shù)的數(shù)字從低到高被不斷地截取，依次作為新的整數(shù)從高到低的各位數(shù)字。 *程序說明與注釋includeincludeint num(int number)。int ok(int number)。int main(){int i,count。printf(There are invertable primes with 4 digits: \n)。for(count=0,i=1001。i9999。i+=2) //窮舉全部的奇數(shù){if(num(i)) //若是可逆素數(shù)，則輸出printf(count%9 ? %3d:%d : %3d:%d\n,++count,i)。}return 0。} int num(int number){int i,j。if(!ok(number))return 0。 //判斷是否為素數(shù)for(i=number,j=0。i0。i/=10) //按位將整數(shù)倒過來，產(chǎn)生反序數(shù){j=j*10 + i%10。}if(numberj) //若原數(shù)小于反序數(shù){if(!ok(i)) //判斷對應(yīng)的反序數(shù)是否為可逆素數(shù){return 0。}else{return 1。 //若是可逆數(shù)素數(shù)，則返回1}}else{return 0。 }getchar()。return 0。}int ok(int number){int i,j。if(number%2 ==0) //判斷是否為素數(shù)return 0。j= sqrt((double)number) +1 。 //取整數(shù)的平方根為判斷的上限for(i=3。ij。i+=2){if(number %i ==0) //若為素數(shù)則返回1，否則返回0return 0。}return 1。}*思考題求1000以內(nèi)的孿生素數(shù)。孿生素數(shù)是指：若a為素數(shù)，且a+2也是素數(shù)，則素數(shù)a和a+2稱為孿生素數(shù)。求不超過1000的回文素數(shù)。*問題分析與算法設(shè)計　　所謂回文素數(shù)是指，對一個整數(shù)n從左向右和從由向左讀其結(jié)果值相同且是素數(shù)，即稱n為回文素數(shù)。所以本題的重點不是判斷素數(shù)的方法，而是求回文整數(shù)。構(gòu)造回文數(shù)的方法很多，這里僅介紹一種最簡單的算法。實現(xiàn)思路是先求出一個整數(shù)的回文數(shù)，再判斷是否為素數(shù)?！　〔怀^1000的回文數(shù)包括二位和三位的回文數(shù)，我們采用窮舉法來構(gòu)造一個整數(shù)并求與其對應(yīng)的反序數(shù)，若整數(shù)與其反序數(shù)相等，則該整數(shù)是回文數(shù)。*程序說明與注釋include int a(int n)int main(){int i,j,t,k,s。printf(Following are palindrome primes not greater than 1000:\n)。for(i=0。i=9。++i) //窮舉第一位for(j=0。j=9。++j) //窮舉第二位for(k=0。k=9。++k) //窮舉第三位{s=i*100 + j*10 + k。 //計算組成的整數(shù)t=ik*100 + j*10 + i。 //計算對應(yīng)的反序數(shù)if(i == 0 amp。amp。 j==0) //處理整數(shù)的前兩位為0的情況{t/100。}else if(i ==0) //處理整數(shù)的第一位為0的情況{t/10。}if( amp。amp。 s==t amp。amp。 a(s)) //若大于10且為回文素數(shù)，則輸出{printf(%d\t,s)。}}return 0。}//判斷參數(shù)n是否為素數(shù)int a(int n){int i。for(i=2。i(n1)/2。+=i){if(n%i == 0)return 0。}return 1。}*運(yùn)行結(jié)果Following are palindrome primes not greater than 1000:11 101 131 151 181 191 313 353373 383 727 787 797 919 929*思考題優(yōu)化生成回文數(shù)的算法。“1898–要發(fā)就發(fā)”。請將不超過1993的所有素數(shù)從小到大排成第一行，第二行上的每個素數(shù)都等于它右肩上的素數(shù)之差。編程求出：第二行數(shù)中是否存在這樣的若干個連續(xù)的整數(shù)，它們的和恰好是1898？假好存在的話，又有幾種這樣的情況？第一行：2 3 5 7 11 13 17……1979 1987 1993第二行：1 2 2 4 2 4…… 8 6*問題分析與算法設(shè)計首先從數(shù)學(xué)上分析該問題：假設(shè)第一行中的素數(shù)為n[1]、n[2]、n[3]….n[i]、…第二行中的差值為m[1]、m[2]、m[3]…m[j]…。其中m[j]為：m[j]=n[j+1]n[j]。則第二行連續(xù)N個數(shù)的和為：SUM=m[1]+m[2]+m[3]+…+m[j]=(n[2]n[1])+(n[3]n[2])+(n[4]n[3])+…+(n[j+1]n[j])=n[j+1]n[1]由此題目就變成了：在不超過1993的所有素數(shù)中是否存在這樣兩個素數(shù)，它們的差恰好是1898。若存在，則第二行中必有所需整數(shù)序列，其和恰為1898。對等價問題的求解是比較簡單的。由分析可知，在素數(shù)序列中不必包含2，因為任意素數(shù)與2的差一定為奇數(shù)，所以不必考慮。*程序與程序注釋：includeincludedefine NUM 320int number[NUM]。 /*存放不超過1993的全部奇數(shù)*/int fflag(int i)。int main(){int i,j,count=0。printf(there are follwing primes sequences in first row:\n)。for(j=0,i=3。i=1993。i+=2) /*求出不超過1993的全部奇數(shù)*/if(fflag(i)) number[j++]=i。for(j–。number[j]1898。j–) /*從最大的素數(shù)開始向1898搜索*/{for(i=0。number[j]number[i]1898。i++)。 /*循環(huán)查找滿足條件的素數(shù)*/if(number[j]number[i]==1898) /*若兩個素數(shù)的差為1898，則輸出*/printf((%d).%3d,…..,%d\n,++count,number[i],number[j])。}}int fflag(int i){int j。if(i=1) return 0。 /*判斷是否為素數(shù)*/if(i==2) return 1。if(!(i%2)) return 0。 /*if no, return 0*/for(j=3。j=(int)(sqrt((double)i)+1)。j+=2)if(!(i%j)) return 0。return 1。}*運(yùn)行結(jié)果There are follwing primes sequences in first row:(1).89,……,1987(2).53,……,1951(3). 3,……,1901*思考題將1,2，3。,20這20個連續(xù)的自然數(shù)排成一圈，使任意兩個相鄰的自然數(shù)之和均為素數(shù)。求四階的素數(shù)幻方。即在一個4X4 的矩陣中，每一個格填 入一個數(shù)字，使每一行、每一列和兩條對角線上的4 個數(shù)字所組成的四位數(shù)，均為可逆素數(shù)。*問題分析與算法設(shè)計有了前面的基礎(chǔ)，本題應(yīng)當(dāng)說是不困難的。最簡單的算法是：采用窮舉法，設(shè)定4X4矩陣中每一個元素的值后，判斷每一行、每一列和兩條對角線上的4個數(shù)字組成的四位數(shù)是否都是可逆素數(shù)，若是則求出了滿足題意的一個解。這種算法在原理是對的，也一定可以求出滿足題意的全部解。但是，按照這一思路編出的程序效率很低，在微機(jī)上幾個小時也不會運(yùn)行結(jié)束。這一算法致命的缺陷是：要窮舉和判斷的情況過多。充分利用題目中的“每一個四位數(shù)都是可逆素數(shù)”這一條件，可以放棄對矩陣中每個元素進(jìn)行的窮舉的算法，先求出全部的四位可逆素數(shù)(204個)，以矩陣的行為單位，在四位可逆素數(shù)的范圍內(nèi)進(jìn)行窮舉，然后將窮舉的四位整數(shù)分解為數(shù)字后，再進(jìn)行列和對角線方向的條件判斷，改進(jìn)的算法與最