12 条题解

  • -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 吧。

信息

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