ural 1356. Something Easier（数论，哥德巴赫猜想）-白红宇

ural 1356. Something Easier（数论，哥德巴赫猜想）

阅读量：7165 次

发布时间：2019-06-29

本文共 3437 字，大约阅读时间需要 11 分钟。

1356. Something Easier

Time limit: 1.0 second

Memory limit: 64 MB

“How do physicists define prime numbers? Very easily: prime numbers are the number 2 and all the odd numbers greater than 2. They may show that this definition corresponds to the mathematical one: 3 is prime, 5 is prime, 7 is prime… 9? 9 is certainly not prime. Then: 11 is prime, 13 is prime. So 9 is the experiment mistake.”

From mathematical analysis course

Once physicist and mathematician argued how many prime numbers one needed for the purpose that their sum was equal to

N. One said that it wasn’t known and the other that 3 was always enough. The question is how many.

Input

The first line contains

T, an amount of tests. Then

T lines with integer

N follow (0 ≤

T ≤ 20; 2 ≤

N ≤ 10 9).

Output

For each test in a separate line you should output prime numbers so that their sum equals to

N. An amount of such prime numbers is to be minimal possible.

Sample

input	output
7227851921498337	223 2 22 8311 1811498337

input

output

7227851921498337

223 2 22 8311 1811498337

题意

一位物理学家和一位数学家正在争论最少几个质数的和为N。其中一个说这无从知晓，另一个说3个就够了。

input

第一行包含一个整数T，表示测试点数量。接下来T行，每行一个整数N。(0<=T<=20,2<=N<=10^9)

output

输出一些质数，使它们的和为N，质数的个数要尽量少。

思路：根据哥德巴赫猜想，

$(A):$ 任一大于2的都可写成两个质数之和。

$(B):$ 任一大于7的奇数都可写成三个素数之和。

详细内容可参照维基百科。

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             7 #include 
            
              8 #include 
              9 #include 
              
                10 #include 
               
                 11 #include 
                
                  12 #include 
                 
                   13 #include 
                  
                    14 #include 
                   
                     15 #include 
                    
                      16 #include 
                     
                       17 #include 
                      
                        18 #include 
                       
                         19 #include 
                        
                          20 #include 
                         
                           21 #include 
                          
                            22 #include 
                           
                             23 using namespace std; 24 25 #define FOR(i,a,b) for(i = (a); i < (b); ++i) 26 #define FORE(i,a,b) for(i = (a); i <= (b); ++i) 27 #define FORD(i,a,b) for(i = (a); i > (b); --i) 28 #define FORDE(i,a,b) for(i = (a); i >= (b); --i) 29 #define max(a,b) ((a) > (b)) ? (a) : (b) 30 #define min(a,b) ((a) < (b)) ? (a) : (b) 31 #define CLR(a,b) memset(a,b,sizeof(a)) 32 #define PB(x) push_back(x) 33 34 typedef long long LL; 35 typedef vector
                            
                              VI; 36 37 const int MAXN = 31623; 38 const int hash_size = 25000002; 39 const int INF = 0x7f7f7f7f; 40 41 bool p[MAXN]={ 0}, flag; 42 int prime[MAXN]={ 0}, q[4], n, d; 43 void init() 44 { 45 int i; 46 for(i = 2; i <= 31622; i++) 47 if(!p[i]) 48 { 49 prime[0]+=1; 50 prime[prime[0]]=i; 51 for(int j=i+i;j<=31622;j+=i) 52 p[j]=true; 53 } 54 } 55 56 bool isprime(int n){ //判断n是否是一个质数 57 if (n == 2) 58 return true; 59 else { 60 int sq, i; 61 sq = int(sqrt(n*1.0)); 62 for (i = 2; i <= sq+1; ++i) 63 if (n%i == 0) 64 return false; 65 return true; 66 } 67 } 68 69 void dfs(int k,int x,int y) 70 { //将奇数进行分解 71 int i; 72 if (flag) return; 73 if (k == 1) 74 { 75 if (isprime(x)) 76 { 77 FORD(i, d, 1) 78 printf("%d ", prime[q[i]]);//进行输出 79 printf("%d\n", x); 80 flag = true;//找到了一个分解 81 } 82 return; 83 } 84 for (i = y; i<=prime[0]; ++i) 85 { 86 if (prime[i]*k > x) return; 87 q[k] = i; 88 dfs(k-1, x-prime[i], i); 89 } 90 } 91 92 int main() 93 { 94 init(); 95 int t, i; 96 scanf("%d", &t); 97 while (t--) { 98 scanf("%d", &n); 99 if (isprime(n))100 printf("%d\n", n);101 else if (n&1) {102 d = 1;103 flag = false;104 while (!flag)105 dfs(++d, n, 1);//先分2分，再分3个106 }107 else {108 int tmp;109 FORE(i, 1, prime[0]) {110 tmp = n - prime[i];111 if (isprime(tmp)) {112 printf("%d %d\n", prime[i], tmp);113 break;114 }115 }116 }117 }118 return 0;119 }

View Code

转载于:https://www.cnblogs.com/zhangchengbing/p/3420215.html

你可能感兴趣的文章