① 求四位可逆素數,所謂的可逆素數是指:一個素數將各位數字的順序反過來也是素數。
//已經修改OK,可能會有兩個警告,可用對k=sqrt(m) ,k=sqrt(str1[i])
//這兩句進行類型轉換即可..不過對運行沒什麼影響...
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main()
{
int str[9001],str1[9001];//應該定義為int類型,另外四位素數有9000,數組大小不合適
int a,b,c,d,i,j=0,k,m,l=0,n=0;
for (m=1000;m<10000;m++)
{ //*********
k=sqrt(m);
for (i=2;i<=k;i++)//判斷應該從2開始,直接對0求余,運行時會報錯
if (m%i == 0)
break;
if (i>k)
{
str[j]=m;
j++;
}
} //*********這部分是存儲四位素數部分,應該擴起來
for (i=0;i<j;i++)
{
a=str[i]/1000;
b=(str[i]%1000)/100;
c=(str[i]%100)/10;
d=str[i]%10;
str1[l]=d*1000+c*100+b*10+a;
l++;
}
for (i=0;i<l;i++)
{
k=sqrt(str1[i]); //應該是數組str1[i]
for (j=2;j<=k;j++)//for循環內層參數與外層相同,均為i,可用j,同樣需從2開始
if (str1[i]%j == 0)//是str1[i]而不是m
break;
if (j>k)
printf("%d\n",str1[i]);//直接輸出即可,不用添加多餘的數組保存
// {
// str2[n]=str1[i];
// n++;
// }
}
// for (i=0;i<n;i++)
// printf("%d\n",str2[i]);
return 0;
}
② c語言輸出所有4位逆序素數,就是把一個四位素數四位倒過來還是素數
#include<stdio.h>
//求四位數的倒序如:1234返回:4321
intgetNum(intyourNum){
inttagNum=0;
while(yourNum>0){
tagNum=tagNum*10+yourNum%10;
yourNum/=10;
}
returntagNum;
}
//求該數是不是素數,是則返回1,否則返回0
intisNum(intyourNum){
intindex;
for(index=2;index<yourNum;index++)
if(yourNum%index==0)
return0;
return1;
}
intmain(){
intindex;
intline=0;//設立換行標志,輸出5個換行
for(index=1000;index<=9999;index++){
if(isNum(index)==1&&isNum(getNum(index))==1){
if(line++%5==0)//輸出5個換行
printf(" ");
printf("%d",index);
}
}
return0;
}
③ 求四位的可逆素數。可逆素數指:一個素數將其各位數字的順序倒過來構成的反序數也
你是想把這些素數列舉出來都有哪些,還是想知道如何編程序找到這些素數??
程序
#include"stdio.h"
#include"math.h"
main()
{
int i,j,k,a[10000];
for(i=0;i<10000;i++)a[i]=1;
for(i=0;i<1000;i++)a[i]=0;
for(i=1000;i<=9999;i++)
{
for(j=2;j<=sqrt(i);j++)
if(i%j==0) {a[i]=0;break;}
k=i%10*1000+i/10%10*100+i/100%10*10+i/1000;
for(j=2;j<=sqrt(k);j++)
if(k%j==0) {a[i]=0;break;}
}
for(i=0;i<=9999;i++)
if(a[i]==1) printf("%6d ",i);
getch();
}
結果看我空間....
④ 求四位的可逆素數,可逆素數指:一個素數將其各位數字的順序倒過來構成的反序數也是素數
#include <stdio.h>
#include <math.h>
int isPrime(int number)
{
int i,n;
i = 2;
n = sqrt(number);
for ( ; i <= n ; ++i )
if ( number % i == 0 )
return 0;
return 1;
}
int convert(int number)
{
int num;
num = 0;
while ( number > 0 )
{
num *= 10;
num += number % 10;
number = number / 10;
}
return num;
}
void main()
{
int i ;
for ( i = 1000; i < 9999; ++i )
if ( isPrime(i) && isPrime(convert(i)) )
printf("%d is reversible prime\n",i);
}
⑤ 初學求四位可逆素數的c語言 有什麼錯誤
偶數不是素數,所以只判斷4位奇數;最高位是偶數的也不是所求之數,故跳過。然後判斷是否為迴文數,是的再判斷是否為素數;是的話輸出這個素數。提供以下參考代碼:
//#include"stdafx.h"//Ifthevc++6.0,withthisline.
#include"stdio.h"
intmain(void){
inti,j,k,f=0;
for(i=1001;i<10000;i+=2){//偶數不是素數,不參與
if((i/1000&1)==0)i+=1000;//最高位是偶數的不是所求之數,跳過
if(i/1000==i%10&&i/100%10==i/10%10){//是迴文數的再判是否為素數
for(j=3;(k=j*j)<=i;j+=2)//判斷素數
if(i%j==0)break;
if(k>i)printf("%d",f=i);//輸出迴文素數
}
}
printf(f?" ":"Thereisnosuchaprimenumber. ");
return0;
}
⑥ C語言可逆素數急急急!求四位可逆素數一個素數和他順序調過來構成的反序也是素數/
for(j=3;j<=(double)sqrt(n)+1;j+=2)這一句改為
for(j=3;j<=(double)sqrt(n);j+=1)
⑦ 這個程序是求四位可逆素數的嗎它的程序代碼又是什麼急求!!!!
求四位可逆素數,正確
⑧ 高手們,幫忙啊,c語言程序設計
*問題分析與演算法設計
最簡單的演算法是:採用窮舉法,設定4X4矩陣中每一個元素的值後,判斷每一行、每一列和兩條對角線上的4個數字組成的四位數是否都是可逆素數,若是則求出了滿足題意的一個解。
這種演算法在原理是對的,也一定可以求出滿足題意的全部解。但是,按照這一思路編出的程序效率很低,在微機上幾個小時也不會運行結束。這一演算法致命的缺陷是:要窮舉和判斷的情況過多。
充分利用題目中的「每一個四位數都是可逆素數」這一條件,可以放棄對矩陣中每個元素進行的窮舉的演算法,先求出全部的四位可逆素數(204個),以矩陣的行為單位,在四位可逆素數的范圍內進行窮舉,然後將窮舉的四位整數分解為數字後,再進行列和對角線方向的條件判斷,改進的演算法與最初的演算法相比,大大地減少了窮舉的次數。
考慮矩陣的第一行和最後一行數字,它們分別是列方向四位數的第一個數字和最後一個數字,由於這些四位數也必須是可逆素數,所以矩陣的每一行和最後一行中的各個數字都不能為偶數或5。這樣窮舉矩陣的第一行和最後一行時,它們的取值范圍是:所有位的數字均不是偶數或5的四位可逆數。由於符合這一條件的四位可逆素數很少,所以這一范圍限制又一次減少了窮舉的次數。
對演算法的進一步研究會發現:當設定了第一和第二行的值後,就已經可以判斷出當前的這種組合是否一定是錯誤的(尚不能肯定該組合一定是正確的)。若按列方向上的四個兩位數與四位可逆數的前兩位矛盾(不是其中的一種組合),則第一、二行的取值一定是錯誤的。同理在設定了前三行數據後,可以立刻判斷出當前的這種組合是否一定是錯誤的,若判斷出矛盾情況,則可以立刻設置新的一組數據。這樣就可以避免將四個數據全部設定好以後再進行判斷所造成的低效。
根據以上分析,可以用偽語言描述以上改進的演算法:
開始
找出全部四位的可逆素數;
確定全部出現在第一和最後一行的四位可逆素數;
在指定范圍 內窮舉第一行
在指定范圍內窮舉第二行
若第一、第二、三行已出現矛盾,則繼續窮舉下一個數;
在指定范圍內窮舉第四行
判斷列和對角方向是否符合題意
若符合題意,則輸出矩陣;
否則繼續窮舉下一個數;
結束
在實際編程中,採用了很多程序設計技巧,假如設置若干輔助數組,其目的就是要最大限度的提高程序的執行效率,縮短運行時間。下面的程序運行效率是比較高的。
*程序說明與注釋
#include<stdio.h>
#include<math.h>
int number[210][5]; /*存放可逆素數及素數分解後的各位數字*/
int select[110]; /*可以放在矩陣第一行和最後一行的素數的下標*/
int array[4][5]; /*4X4的矩陣,每行0號元素存可逆素數對應的數組下標*/
int count; /*可逆素數的數目*/
int selecount; /*可以放在矩陣第一行和最後一行的可逆素數的數目*/
int larray[2][200]; /*存放素數前二、三位數的臨時數組所對應的數量計數器*/
int lcount[2];
int num(int number);
int ok(int number);
void process(int i);
void _num(int i);
int comp_num(int n);
int find1(int i);
int find2(void);
int find0(int num);
void p_array(void);
int main()
{
int i,k,flag,cc=0,i1,i4;
printf("there are magic squares with invertable primes as follw:\n");
for(i=1001;i<9999;i+=2) /*求滿足條件的可逆素數*/
{
k=i/1000;
if(k%2!=0&&k!=5&&num(i)) /*若可逆素數的第一位不是偶數或5*/
{
number[count][0]=i; /*存入數組*/
process(count++); /*分解素數的各位數字*/
if(number[count-1][2]%2!=0&& /*若可逆素數滿足放在矩陣第一行*/
number[count-1][3]%2!=0&& /*和最後一行的條件,記錄可逆素數的*/
number[count-1][2]!=5&& /*下標,計數器加1*/
number[count-1][3]!=5)
select[selecount++]=count-1;
}
}
larray[0][lcount[0]++]=number[0][0]/100; /*臨時數組的第一行存前二位*/
larray[1][lcount[1]++]=number[0][0]/10; /*臨時數組的第二行存前三位*/
for(i=1;i<count;i++) /*將素數不重復的前二、三位存入臨時數組中*/
{
if(larray[0][lcount[0]-1]!=number[i][0]/100)
larray[0][lcount[0]++]=number[i][0]/100;
if(larray[1][lcount[1]-1]!=number[i][0]/10)
larray[1][lcount[1]++]=number[i][0]/10;
}
for(i1=0;i1<selecount;i1++) /*在第一行允許的匯聚圍內窮舉*/
{
array[0][0]=select[i1]; /*取對應的素數下標*/
_num(0); /*復制分解的素數*/
for(array[1][0]=0;array[1][0]<count;array[1][0]++) /*窮舉第二行*/
{
_num(1); /*復制分解的數字*/
if(!comp_num(2))
continue; /*若每列的前兩位的組成與素數相矛盾,則試探下一個數*/
for(array[2][0]=0;array[2][0]<count;array[2][0]++) /*窮舉第三行*/
{
_num(2); /*復制分解的數字*/
if(!comp_num(3))
continue; /*若每列的前三位的組成與素數相矛盾,則試探下一個數*/
for(i4=0;i4<selecount;i4++) /*在最後一行允許的范圍內窮舉*/
{
array[3][0]=select[i4];
_num(3); /*復制分解的數字*/
for(flag=1,i=1;flag&&i<=4;i++) /*判斷每列是否可逆素數*/
if(!find1(i))flag=0;
if(flag&&find2()) /*判斷對角線是否為可逆素數*/
{ printf("No.%d\n",++cc); p_array(); } /*輸出幻方矩陣*/
}
}
}
}
}
int num(int number) /*判斷是否可逆素數*/
{
int j;
if(!ok(number)) return 0;
for(j=0;number>0;number/=10) /*將素數變為反序數*/
j=j*10+number%10;
if(!ok(j)) return 0; /*判斷反序數是否為素數*/
return 1;
}
int ok(int number) /*判斷是否為素數*/
{
int i,j;
if(number%2==0) return 0;
j=sqrt((double)number)+1;
for(i=3;i<=j;i+=2)
if(number%i==0) return 0;
return 1;
}
void process(int i) /*將第i個整數分解為數字並存入數組*/
{
int j,num;
num=number[i][0];
for(j=4;j>=1;j--,num/=10)
number[i][j]=num%10;
}
void _num(int i) /*將array[i][0]指向的素數的各位數字復制到array[i]中*/
{
int j;
for(j=1;j<=4;j++)
array[i][j]=number[array[i][0]][j];
}
int comp_num(int n) /*判斷array中每列的前n位是否與可逆素數允許的前n位矛盾*/
{
static int ii; /*用內部靜態變數保存前一次查找到的元素下標*/
static int jj; /*ii:前一次查找前二位的下標,jj:前一次查找前三位的下標*/
int i,num,k,*p; /*p:指向對應的要使用的前一次下標ii或jj*/
int *pcount; /*pcount:指向要使用的臨時數組數量的計數器*/
switch(n){ /*根據n的值選擇對應的一組控制變數*/
case 2:pcount=&lcount[0];p=ⅈbreak;
case 3:pcount=&lcount[1];p=&jj;break;
default:return 0;
}
for(i=1;i<=4;i++) /*對四列分別進行處理*/
{
for(num=0,k=0;k<n;k++) /*計算前n位數字代表的數值*/
num=num*10+array[k][i];
if(num<=larray[n-2][*p]) /*與前一次最後查找到的元素進行比較*/
for(;*p>=0&&num<larray[n-2][*p];(*p)--);/*若前次查找到的元素大,則向前找*/
else
for(;p<pcount&&num>larray[n-2][*p];(*p)++); /*否則向後找*/
if(*p<0||*p>=*pcount)
{
*p=0; return 0;
}
if(num!=larray[n-2][*p])
return 0; /*前n位不是可逆素數允許的值則返回0*/
}
return 1;
}
int find1(int i) /*判斷列方向是否是可逆素數*/
{
int num,j;
for(num=0,j=0;j<4;j++)
num=num*10+array[j][i];
return find0(num);
}
int find2(void) /*判斷對角線方向是否是可逆素數*/
{
int num1,num2,i,j;
for(num1=0,j=0;j<4;j++)
num1=num1*10+array[j][j+1];
for(num2=0,j=0,i=4;j<4;j++,i--)
num2=num2*10+array[j][i];
if(find0(num1)) return(find0(num2));
else return 0;
}
int find0(int num) /*查找是否為滿足要求的可逆素數*/
{
static int j;
if(num<=number[j][0])for(;j>=0&&num<number[j][0];j--);
else for(;j<count&&num>number[j][0];j++);
if(j<0||j>=count){ j=0;return 0; }
if(num==number[j][0]) return 1;
else return 0;
}
void p_array(void) /*輸出矩陣*/
{
int i,j;
for(i=0;i<4;i++)
{
for(j=1;j<=4;j++) printf("%d ",array[i][j]);
printf("\n");
}
}
*問題的進一步討論
程序中大量技巧是用於盡早發現矛盾,減少循環次數,縮短運行時間。從實際效果看是相當不錯的。但目前的程序仍然可以進一步優化。
當第四行設定了前三行後,尚未設定的行就沒必要再使用窮舉的方法,因為列方向設定好的三位數字已經限制了最後一個數字可能的取值,在可逆數中找出前三位數字與設定好的三位數字相同的素數。這些素數就是在這一列前面已設定好的三位數字的限制條件下可能的取值。此時每一列上只有不超過四個可能的取值。找出全部各列可能的取值(可能的四位可逆素數),求出它們的交集。若交集為空,即沒有共同的可能取值,則列間數據相互矛盾否滿足則將交集中的數據填 入矩陣中就是題目的一個解。
演算法可再進一步優化。先窮舉一、二和四列的數據,然後用上面的演算法來確定第三行的值,這樣可進一步縮小窮舉的范圍,提高運行效率。
分析輸出的結果。可以看出本題的基本解只有17種,每個解可通過旋轉與反射獲得同構的其它7個解,可以進一步改進程序,只輸出17個基本解。
⑨ C語言求四位可逆素數
#include"stdio.h"
intprime(intn){//素數判斷
inti;
if(!(n&1))
return0;
for(i=3;i*i<=n;i+=2)
if(!(n%i))
return0;
return1;
}
intmain(intargc,char*argv[]){
intn,k;
for(k=0,n=1001;n<10000;n+=2)
if(prime(n)&&prime(n/1000+n/100%10*10+n/10%10*10+n%10*10))
printf(++k%10?"%5d":"%5d ",n);
if(k%10)
printf(" ");
return0;
}
運行結果: