We Chall-Prime Factory-Writeup。本站提示廣大學習愛好者:(We Chall-Prime Factory-Writeup)文章只能為提供參考,不一定能成為您想要的結果。以下是We Chall-Prime Factory-Writeup正文
MarkdownPad Document
We Chall-Prime Factory-Writeup標題鏈接:http://www.wechall.net/challenge/training/prime_factory/index.php
網站翻開較慢,所以把標題放在下方:
Prime Factory (Training, Math)Your task is simple:
Find the first two primes above 1 million, whose separate digit sums are also prime.
As example take 23, which is a prime whose digit sum, 5, is also prime.
The solution is the concatination of the two numbers,
Example: If the first number is 1,234,567
and the second is 8,765,432,
your solution is 12345678765432
粗心就是找到兩個數,這兩個數契合:是大於1000000的質數,並且數字的每一位加起來仍是質數,如:23是質數,2+3=5仍是質數;
由於沒有時間的限制,所以用C++寫了一個暴力循環的代碼:
1 #include<iostream> 2 #include<cmath> 3 using namespace std; 4 typedef long long LL; 5 const LL MILLION = 1000000; 6 7 bool IsPrime_1(LL num) 8 { 9 for(int i = 2; i <= sqrt(num); i++) 10 if(!(num % i)) 11 return 0;//num不是質數 12 13 return 1;//num是質數 14 } 15 16 bool IsPrime_2(LL num) 17 { 18 LL sum = 0; 19 while(num) 20 { 21 sum += num % 10; 22 num /= 10; 23 } 24 25 if(IsPrime_1(sum)) 26 return 1;//各位數字的和仍為質數 27 else 28 return 0; 29 } 30 31 int main() 32 { 33 // LL num; 34 // cin>>num; 35 // if(IsPrime_1(num)) 36 // cout<<1<<endl; 37 // if(IsPrime_2(num)) 38 // cout<<2<<endl; 39 for(LL i = MILLION+1 , cnt = 0 ; cnt < 2 ; i++) 40 { 41 if(IsPrime_1(i)) 42 if(IsPrime_2(i)) 43 { 44 cnt++; 45 cout<<i<<endl; 46 } 47 } 48 49 return 0; 50 }
運轉後果如下:
依據要求的方式得flag為:10000331000037
令:因ABO暫不熟習flag,所以用了較繁瑣的C++,同時由於沒無限制時間,所以寫了暴力循環的代碼,當前熟習python之後,會更新更為簡約的python代碼;
2017-2-5 12:40;11