Codeforces 735 D

​​傳送門​​

題目大意

将一個數字分解成若幹個數字相加，求分解後的每一個數字的最大因子之和（最大因子不包括本身）

思路

代碼

bool vis[maxn];//标記非素數,0是素數
int primer[maxn/10];//存素數
int cnt=0;//記錄素數個數，
void find_primer(){
    for(int i=2;i<=maxn;i++){
        if(!vis[i])primer[cnt++]=i;
        for(int j=0;j<cnt&&primer[j]*i<=maxn;j++){
            vis[i*primer[j]]=1;//篩
            if(i%primer[j]==0)break;//關鍵！！！找到i*primer[j]的最小質因子primer[j]，退出
        }
    }
}

int sushu(ll n){
    for(int i=2;i*i<=n;i++){
        if(n%i==0)return 0;
    }
    return 1;
}

 
int main(){
    ll n;
    find_primer();
    scanf("%lld",&n);
    if(n==2){
        puts("1");
        return 0;
    }
    if(sushu(n)){
        printf("1");
    }
    else{
        if(n%2){
            int flag=0;
            for(int i=0;i<cnt&&primer[i]<=n;i++){
                ll xx=n-primer[i];
                if(xx>primer[cnt-1]){
                    if(sushu(xx)){
                        puts("2");
                        flag=1;
                        break;
                    }
                }
                else{
                    if(vis[xx]==0){
                        puts("2");
                        flag=1;
                        break;
                    }
                }
            }
            if(!flag){
                puts("3");
            }
        }
        else{
            puts("2");
        }
    }
}