程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 題目24: 素數距離問題

題目24: 素數距離問題

編輯:C++入門知識

描述 現在給出你一些數,要求你寫出一個程序,輸出這些整數相鄰最近的素數,並輸出其相距長度。如果左右有等距離長度素數,則輸出左側的值及相應距離。 如果輸入的整數本身就是素數,則輸出該素數本身,距離輸出0  輸入 第一行給出測試數據組數N(0<N<=10000) 接下來的N行每行有一個整數M(0<M<1000000), 輸出 每行輸出兩個整數 A B. 其中A表示離相應測試數據最近的素數,B表示其間的距離。 樣例輸入 3 6 8 10樣例輸出 5 1 7 1 11 1來源 經典題目         [cpp]  /*********************************  *   日期:2013-3-26  *   作者:SJF0115  *   題號: 題目24: 素數距離問題  *   來源:http://acm.nyist.net/JudgeOnline/problem.php?pid=24  *   結果:AC  *   來源:南陽理工OJ  *   總結:  **********************************/   #include<stdio.h>    #include<string.h>    #include<math.h>       #define MAX 1000010    int prime[MAX];   //素數表    void Prime(){       memset(prime,0,sizeof(prime));       for(int i = 2;i < sqrt(MAX)+1;i++){           if(prime[i]){               continue;           }           else{               for(int j = i*i;j < MAX;j += i){                   prime[j] = 1;               }           }       }   }   int main()   {       int N,M,LIndex,RIndex;       //freopen("C:\\Users\\SJF\\Desktop\\acm.txt","r",stdin);        Prime();       prime[1] = 1;       prime[0] = 1;       scanf("%d",&N);       //N組測試數據        while(N--){           scanf("%d",&M);           if(prime[M] == 0){               printf("%d 0\n",M);           }           else{               RIndex = M;               LIndex = M;               //尋找左邊素數                while(prime[LIndex] == 1 && LIndex >= 0){                   LIndex --;               }               //尋找右邊素數                while(prime[RIndex] == 1){                   RIndex ++;               }               //左邊沒有找到                if(LIndex < 0){                   printf("%d %d\n",RIndex,RIndex-M);               }               //左右都有                else if(M - LIndex <= RIndex - M){                   printf("%d %d\n",LIndex,M-LIndex);               }               else{                   printf("%d %d\n",RIndex,RIndex-M);               }           }       }       return 0;   }     /********************************* *   日期:2013-3-26 *   作者:SJF0115 *   題號: 題目24: 素數距離問題 *   來源:http://acm.nyist.net/JudgeOnline/problem.php?pid=24 *   結果:AC *   來源:南陽理工OJ *   總結: **********************************/ #include<stdio.h> #include<string.h> #include<math.h>   #define MAX 1000010 int prime[MAX]; //素數表 void Prime(){ memset(prime,0,sizeof(prime)); for(int i = 2;i < sqrt(MAX)+1;i++){ if(prime[i]){ continue; } else{ for(int j = i*i;j < MAX;j += i){ prime[j] = 1; } } } } int main() { int N,M,LIndex,RIndex; //freopen("C:\\Users\\SJF\\Desktop\\acm.txt","r",stdin); Prime(); prime[1] = 1; prime[0] = 1; scanf("%d",&N); //N組測試數據 while(N--){ scanf("%d",&M); if(prime[M] == 0){ printf("%d 0\n",M); } else{ RIndex = M; LIndex = M; //尋找左邊素數 while(prime[LIndex] == 1 && LIndex >= 0){ LIndex --; } //尋找右邊素數 while(prime[RIndex] == 1){ RIndex ++; } //左邊沒有找到 if(LIndex < 0){ printf("%d %d\n",RIndex,RIndex-M); } //左右都有 else if(M - LIndex <= RIndex - M){ printf("%d %d\n",LIndex,M-LIndex); } else{ printf("%d %d\n",RIndex,RIndex-M); } } } return 0; }  

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved