寝癖頭の解法

学習中の覚え書きを投稿、更新していきます。

ゴールドバッハ予想について

ゴールドバッハ予想についての話です。
きっかけは、paizaラーニングのレベルアップ問題集「素数メニュー」からの出題でした。
paiza.jp

ゴールドバッハ予想とは、Wikipediaによれば...
「全ての 2 よりも大きな偶数は2つの素数の和として表すことができる」
この予想は、4 × 10^18 までの全ての偶数について成り立つことがコンピュータによって確かめられていて、一般に正しいと想定されているが、まだ証明されていないそうです。
ja.wikipedia.org
予想には、ほとんど同値ないくつかの述べ方があり、次のように述べることが多い:
・4以上の全ての偶数は、二つの素数の和で表すことができる。
・6以上の全ての偶数は、二つの奇素数の和で表すことができる。(4=2+2:偶素数同士の和)
このとき、同じ素数を2度使っても良いものとする。

ゴールドバッハ予想と呼ばれるのは、1742年6月7日にクリスティアンゴールドバッハレオンハルト・オイラーへの手紙で述べた、上と同値な次のような予想について...
「5より大きな任意の自然数は、三つの素数の和で表せる」
これから上が導けるのは、偶数を三つの素数の和で表すと素数の一つは 2 になっているからで、たしかに題意は同じと考えられます。
・奇数+奇数+奇数=奇数
・和が偶数になるには、奇数+奇数+偶数 or 偶数+偶数+偶数

そして、paizaラーニングのレベルアップ問題集「素数メニュー」の出題では...
「全ての 3 よりも大きな偶数は 2 つの素数の和として表すことができる」
として、「10^5 以下の偶数 N が与えられるので、 N を 2 つの素数の和で表し、出力してください」という出題でした。
なるほど、面白い、やろう!

僕が作成、提出したコードは、以下のとおりです。

ゴールドバッハ予想

/*
C++による「素数メニュー」問題集
ゴールドバッハ予想
https://paiza.jp/works/mondai
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
bool prime(ll n){
    for(ll i=2;i<=sqrt(n);i++){
        if(n%i==0){
            return false;
        }
    }
    return true;
}
int main(void){
    ll n;
    cin>>n;
    vector<pair<ll,ll>> v;
    vector<ll> vi;
    for(ll i=2;i<n;i++){
        if(prime(i)==true){
            if(prime(n-i)==true){
                v.push_back(pair(i*(n-i),i));
            }
        }
    }
    sort(v.rbegin(),v.rend());
    ll ans=v[0].second;
    if(ans>n-ans){
        cout<<n-ans<<endl;
        cout<<ans<<endl;
    }else{
        cout<<ans<<endl;
        cout<<n-ans<<endl;
    }
    return 0;
}

「ただし、答えが複数個ある場合は、それらのうち、積が最も大きくなるような 2 つの素数を出力してください」
(答えは 1 通りになることが保証されます)

類似の予想としては、「弱いゴールドバッハ予想」というものがあって...
「5より大きい奇数は三つの素数の和で表せる」
論理的に、4より大きい偶数が二つの奇素数の和で表せるという「強いゴールドバッハ予想」が正しいならば、弱いゴールドバッハ予想も真(正しい)となるわけです。
このような「ならば」は、含意(implication)と呼ばれて、含意の命題「AならばB(" A only if B")」を記号で表すと、「A⇒B」と書ける、数学における定理の基本形です。

paizaラーニングのレベルアップ問題集については、ユーザー同士で解答を教え合ったり、コードを公開したりするのは自由としています。
また授業や研修、教材などにも利用できるそうです。