12 条题解

  • 22
    @ 2022-2-8 16:49:48

    较为基础的题目。

    int n;
    bool prime[1000010];
    
    void ensure_prime() {
      memset(prime, true, sizeof(prime));
      prime[0] = false;
      prime[1] = false;
      for (int i = 2; i <= 1000000; i++) {
        if (!prime[i]) continue;
        for (int j = 2; j <= 1000010; j++) {
          if (i * j < 1000010) prime[i * j] = false;
          else break;
        }
      }
    }
    
    int main() {
      ensure_prime(); // 考虑到数据范围较大,需要提前预计算质数列表
      cin >> n;
      while (n) { // 如果为 0 则退出
        for (int i = 3; i <= 1000010; i += 2) {
          if (prime[i] && prime[n - i]) {
            cout << n << " = " << i << " + " << n - i << endl;
            break;
          }
        }
        cin >> n;
      }
      return 0;
    }
    
  • 5
    @ 2023-1-3 9:21:58

    因为题目说了,是任何大于4 的偶数都可以拆成两个奇素数之和,所以不需要特判有2的情况。

    证明

    前置结论:一个偶数可以被拆成两个奇数相加或两个偶数相加,但不能被拆成一个奇数和一个偶数相加。(请自行证明,很容易)

    因为:唯一的偶素数是2,

    所以:一个偶数能被拆成两个偶素数相加,当且仅当这个偶数是4(=2+2)。

    因为:一个偶数可以被拆成两个奇数相加或两个偶数相加,但不能被拆成一个奇数和一个偶数相加,

    又因为:由两个偶素数相加得到的数只有4,不在题目的数据范围内,

    所以:在题目的数据范围内,一个偶数只能被拆成两个奇素数相加。

    因为:在题目的数据范围内,一个偶数只能被拆成两个奇素数相加,

    又因为:2是偶数,

    所以:在题目的数据范围内,我们不需要考虑2。

    代码

    说了这么多,上!代!码! (其实因为证明中提到了,在题目的数据范围内,一个偶数只能被拆成两个奇素数相加,所以有偶数的情况代码中直接跳过)

    #include<iostream>
    using namespace std;
    bool isprime(int x){
        if(x<=1)    return false;
        for(int i=3;i*i<=x;i+=2){
            if(x%i==0) return false;
        }
        return true;
    }
    int main(){
        int n;
        while(cin >> n && n){
            cout << n << " = ";
            int p=3;
            while(!isprime(p) || !isprime(n-p)) p+=2;
            cout << p << " + " << n-p << '\n';
        }
        return 0;
    }
    

    时间复杂度

    O(Tnn)O(Tn\sqrt n),稍稍卡了一下常,时间是正常这个时间复杂度做法的14\frac{1}{4}

    • 3
      @ 2022-11-26 11:34:41

      按照思路枚举模拟即可。#5竟然给我过了。

      #include <bits/stdc++.h>
      #define min(a, b) (a<b ? a : b)
      #define max(a, b) (a>b ? a : b)
      using namespace std;
      
      int n;
      
      bool isPrime(int x){ // 简单的判断质数,新手必会
      	for (int i=2; i*i<=x; i++)
      		if (x%i==0) return false;
      	return true;
      }
      
      void print(int a){
      	for (int i=3; i<=a-2; i+=2){ // 特判2的情况
      		if (isPrime(i) && i==a-2){
                  cout<<a<<" = 2 + "<<i<<endl;
      			return;
      		}
      	}
      	for (int i=3; i<=a-3; i+=2){ // 一般情况
      		if (isPrime(i) && isPrime(a-i)){
                  cout<<a<<" = "<<min(a-i, i)<<" + "<<max(a-i, i)<<endl;
      			return;
      		}
      	}
      }
      
      int main(){
      	while (cin>>n && n/*这一步是为了结束输入,完整写法为n!=0*/) print(n);
      	return 0;
      }
      
      • 2
        @ 2021-11-3 20:07:34

        一道基础的题目。

        观察n<=10^6,所以可以先用线性筛把质数先全部预处理出来。

        对于每个n暴力枚举每个质数,如果n-p[i]也是质数则输出,易证这是符合题目要求b-a最大的解。

        CODE

        bj[1]=1;
        
        for (int i=2;i<=N;i++) { // 线性筛
        
        	if (!bj[i]) p[++tot]=i;
        
        	for (int j=1;j<=tot&&p[j]*i<=N;j++) bj[i*p[j]]=1;
        
        } scanf("%d",&n);
        
        while (n) {
        
        	for (int i=1;i<=tot&&p[i]<n;i++)
        
        		if (!bj[n-p[i]]) {printf("%d = %d + %d\n",n,p[i],n-p[i]); break;}
        
        	scanf("%d",&n);
        
        }
        
        • 1
          @ 2024-10-7 13:13:57

          首先写一个判断素数的布尔型函数。 输入用死循环,后面可以判断x是否为0,直接return 0。 判断时用函数来处理a和x-a两个数就ok了

          #include<bits/stdc++.h>
          using namespace std;
          bool su(int a){
          	if(a<2) return false;
          	for(int i=2;i*i<=a;i++){
          		if(a%i==0){
          			return false;
          		}
          	}
          	return true;
          }
          int main(){
              
              while(true){
                  int a=3;
                  int x;
                  cin >> x;
                  if(x==0) return 0;
                  cout<<x<< " = ";
                  int n=x-3;
                  while(a<=n){
                      if(su(a) and su(x-a)){
                          cout << a << " + " << x-a << endl;
                          break;
                      }
                      a+=2;
                  }
              }
              return 0;
          }
          
          • 1
            @ 2024-3-31 19:20:11

            时间复杂度较高,但是简单易懂。

            #include<iostream>
            using namespace std;
            const int maxl = 20;
            int n = 1,a[maxl];
            bool isprime(int m)
            {
            	if(m==1)return false;
            	for(int i=2;i*i<=m;i++)if(m%i==0)return false;
            	return true;
            }
            int main()
            {
            	while(cin>>a[n]&&a[n]!=0)n++;
            	for(int i=1;i<=n-1;i++)
            	{
            		bool flag = 1;
            		for(int j=3;j<=a[i]/2;j++)
            		{
            			if(isprime(j)&&isprime(a[i]-j))
            			{
            				cout<<a[i]<<" = "<<j<<" + "<<a[i]-j<<endl;
            				flag = 0;
            				break;
            			}
            		}
            		if(flag)cout<<"Goldbach's conjecture is wrong\n";
            	}
            	return 0;
            }
            
            • 0
              @ 2023-1-21 12:42:20

              解决这道题很简单,筛法都不用,详情见代码:

              #pragma GCC optimize(2)
              #include<bits/stdc++.h>
              using namespace std;
              #define int long long
              int n;
              bool isPrime(int x){
              	if(x<2)return false;
              	for(int i=2;i*i<=x;i++){
              		if(x%i==0)return false;
              	}return true;
              }
              signed main(){
              	ios::sync_with_stdio(false);
              	cin.tie(0);
              	cout.tie(0);
              	while(cin>>n){
              		if(n==0)break;
              		cout<<n<<" = ";
              		for(int i=3;i<=n;i++){
              			if(isPrime(i)&&isPrime(n-i)){
              				cout<<i<<" + "<<n-i<<endl;
              				break;
              			}
              		}
              	}
              	return 0;
              }
              
              • 0
                @ 2022-5-29 16:04:56

                这道题我们可以循环输入n,直到n为0。对于每次输入暴力枚举每个相加是n的数,接着判断它们是否都是质数。

                #include<bits/stdc++.h>
                using namespace std;
                bool isprime(int n){//质数判断函数
                	if(n==0 or n==1){//0和1特判
                		return 0;
                	}
                	for(int i=2;i<n;i++){//枚举因数
                		if(n%i==0)return 0;//有除了1以外的因数就返回0
                	}
                	return 1;//返回1
                }
                int n=-1;//否则不会进while循环
                int main(){
                    while(n!=0){//循环
                    	cin>>n;
                    	if(n==0){//是0就退出
                    		break;
                		}
                		for(int i=0;i<=n;i++){//枚举加数
                			if(isprime(i) and isprime(n-i)){
                				cout<<n<<" = "<<i<<" + "<<n-i<<endl;//输出,注意格式
                				break;//找到就退出
                			}
                		}
                	}
                	return 0; 
                }
                
                • 0
                  @ 2022-4-25 19:13:39

                  使用一般的算法来解题:

                  #include<bits/stdc++.h>
                  using namespace std;
                  bool is_prime(int n)
                  {
                  	for (int i=2;i*i<=n;i++)
                  	{
                  		if (n%i==0)
                  		{
                  			return 0;
                  		}
                  	}
                  	return 1;
                  }
                  int main()
                  {
                  	int n,i;
                  	while (cin>>n&&n!=0)
                  	{
                  		i=3;
                  		while (is_prime(i)==0||is_prime(n-i)==0)
                  		{
                  			i+=2;
                  		}
                  		printf("%d = %d + %d\n",n,i,n-i);
                  	}
                  	return 0;
                  }
                  
                  • -1
                    @ 2023-9-27 12:28:49

                    👍 可爱可爱可爱

                    • -2
                      @ 2022-5-1 17:31:09

                      一道很简单的题目,上代码:

                      #include <iostream>
                      #include <algorithm>
                      using namespace std;
                      bool is_prime(int x) {
                          if (x < 2 || (x > 2 && x % 2 == 0)) return false;
                          for (int i = 3; i * i <= x; ++i)
                              if (x % i == 0) return false;
                          return true;
                      }
                      int main() {
                          int n;
                          while (~scanf("%d", &n)) {
                              if (n == 0) break;
                              bool flag = false;
                              for (int i = 3; i <= n / 2; i += 2)
                                  if (is_prime(i) && is_prime(n - i)) {
                                      printf("%d = %d + %d\n", n, min(i, n - i), max(i, n - i));
                                      flag = true;
                                      break;
                                  }
                              if (!flag) puts("Goldbach's conjecture is wrong.");
                          }
                          return 0;
                      }
                      

                      基础知识:质数(素数)的判断

                      • -3
                        @ 2022-3-28 11:25:08

                        这么简单的题目,何必写那么复杂呢?

                        #include <iostream>
                        using namespace std;
                        bool zhi(int a){
                        	if(a<=1)return false;
                        	for(int i=2;i*i<=a;i++)if(a%i==0)return false;
                        	return true;
                        }
                        int main(){
                        	int n;
                        	cin>>n;
                        	if(n==0)return 0;
                        	for(int i=1;i*2<=n;i++)if(zhi(i)&&zhi(n-i)){cout<<n<<" = "<<i<<" + "<<n-i<<endl;break;}
                        	return main();
                        }
                        
                        • @ 2022-11-11 19:48:27

                          复杂度错的吧,你的第一层循环枚举一个 ii 需要 O(n)O(n) 的时间,然后你还得判断 ii 是否为素数,总时间复杂度为 O(nn)O(n\sqrt n),显然这个时间复杂度无法通过 n106n\le 10^6 吧。

                      • 1

                      信息

                      ID
                      197
                      时间
                      1000ms
                      内存
                      256MiB
                      难度
                      2
                      标签
                      递交数
                      580
                      已通过
                      218
                      上传者