9 solutions

  • 8
    @ 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;
    }
    
  • 3
    @ 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}

    • 2
      @ 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;
      }
      
      • 1
        @ 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);
        
        }
        
        • 0
          @ 2023-1-21 12:42:20

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

          #pragma GCC optmize(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
                @ 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;
                }
                

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

                • -2
                  @ 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

                Information

                ID
                197
                Time
                1000ms
                Memory
                256MiB
                Difficulty
                2
                Tags
                # Submissions
                195
                Accepted
                80
                Uploaded By