质因子进化

· · 个人记录

1742年6月7日，哥德巴赫写信给欧拉，提出了以下的猜想：任何一个大于9的奇数都可以表示成3个质数之和。

欧拉在回信中说，他相信这个猜想是正确的，但他不能证明。

从此，这道数学难题引起了几乎所有数学家的注意。哥德巴赫猜想由此成为数学皇冠上一颗可望不可及的“明珠”。

题目内容表述

先给出一个奇数，要求输出3个质数，这 3 个质数之和等于输入的奇数。

编一个程序验证哥德巴赫猜想。

输入仅有一行，包含一个在long long范围内正奇数，。

输出仅有一行，输出3个质数，这3个质数之和等于输入的奇数。相邻两个质数之间用一个空格隔开，最后一个质数后面没有空格。如果表示方法不唯一，请输出第一个质数最小的方案，如果第一个质数最小的方案不唯一，请输出第一个质数最小的同时，第二个质数最小的方案。

以下是我的代码：

#include<bits/stdc++.h>
using namespace std;
long long n;
bool zhi(long long x){//是否为质数 
    if(x<2||x%2==0&&x!=2||x%3==0&&x!=3||x%5==0&&x!=5||x%7==0&&x!=7||x%11==0&&x!=11||x%13==0&&x!=13)
    return 0;
    if(x<4||x==5||x==7||x==11||x==13)
    return 1;
    if(x<17)
        return 0;
    for(long long i=18;i-1<=sqrt(x)&&i-1<=x/17;i+=6){
    if(i-1<=x/17&&x%(i-1)==0)
            return 0;
    if(i+1<=sqrt(x)&&i+1<=x/17&&x%(i+1)==0)
        return 0;
    }
    return 1;
}
int main(){
    cin>>n;
    if(zhi(n-4)){
    cout<<"2 2 "<<n-4;
    return 0;
    }
    for(long long i=3;i<=n/3;i+=2)
    for(long long j=i;j<=(n-i)/2;j+=2)
            if(zhi(i)&&zhi(j)&&zhi(n-i-j)){
            cout<<i<<" "<<j<<" "<<n-i-j;
        return 0;
        }
    return 0;
}

再做优化：

#include<bits/stdc++.h>
using namespace std;
long long n;
bool zhi(long long x){//是否为质数 
    if(x<2||x%2==0&&x!=2||x%3==0&&x!=3||x%5==0&&x!=5||x%7==0&&x!=7||x%11==0&&x!=11||x%13==0&&x!=13)
    return 0;
    if(x<4||x==5||x==7||x==11||x==13)
    return 1;
    if(x<17)
        return 0;
    for(long long i=18;i-1<=sqrt(x)&&i-1<=x/17;i+=6){
    if(i-1<=x/17&&x%(i-1)==0)
            return 0;
    if(i+1<=sqrt(x)&&i+1<=x/17&&x%(i+1)==0)
        return 0;
    }
    return 1;
}
int main(){
    cin>>n;
    if(zhi(n-4)){
    cout<<"2 2 "<<n-4;
    return 0;
    }
    cout<<"3 ";
    for(long long i=3;i<=n/3;i+=2)
        if(zhi(i)&&zhi(n-i-3)){
        cout<<j<<" "<<n-i-j;
        return 0;
    }
    return 0;
}

再做那么一点点优化：

inline bool zhi(long long x){
    if(x>4&&x%6%4!=1||x<2||x%2==0&&x!=2||x%3==0&&x!=3||x%5==0&&x!=5||x%7==0&&x!=7||x%11==0&&x!=11||x%13==0&&x!=13)
    return 0;
    if(x<4||x==5||x==7||x==11||x==13)
    return 1;
    if(x<17)
    return 0;
    for(long long i=18;i-1<=sqrt(x)&&i-1<=x/17;i+=6){
    if(i-1<=x/17&&x%(i-1)==0)
            return 0;
    if(i+1<=sqrt(x)&&i+1<=x/17&&x%(i+1)==0)
        return 0;
    }
    return 1;
}

依此模板，可做质因子等题。且可优化许多，去除一些不必要的，可以依据质数是质数（没什么意义，本来就是这样的），质数之倍数，此倍数非本身之质数。而后扩倍可得结论。

但还可以做优化，思路如下：

比如，2、3均为质数，2、3为至小的两个质数。

此时，先看1的倍数,1、2、3······1不为质数，2为质数，3为质数。

2的2倍及以上：4、6、8、10、12······

3的2倍及以上：6、9、12、15、12······

2、3均为质数，所以除2、3外，只有取余2、3的最小公倍数为1或5的数方 可能（仅仅是有可能） 为质数。

故，除已知质数，一个数取余已知质数的最小公倍数不为任意一个已知质数之倍数，则此数可能为质数。

在1至最大已知质数的二次方这个范围内，一个数取余已知质数的最小公倍数不为1至最大已知质数的任意一个质数之倍数，则此数可能为质数。

已知质数需从2至3，从第一个质数到第二个质数，从一个质数到下一个质数，至少可以知道1至最大已知质数的2次方中的任意正整数是否为质数，所有数都知道，不过请注意，要确定1至最大已知质数中的任意正整数是否为质数较难。

以此，可简单地不断“进化”，如“进化”算法般，但最好先确定质数2来“进化”。

此为吾所思之质之理。