CF1076B Divisor Subtraction

题目大意：
   输入n，不断将n赋值为n-p（p为n的最小质因数），问减多少次n=0。(2≤n≤10¹⁰).

思路：

    偶数的最小质因子为2，并且减之后还一直为2；奇数的最小质因子一定是奇数，相减后变为2。

 

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int  maxn=100000;
int pri[maxn+10],prin;
long long n;
bool shaizi[maxn+10];

void init()
{
    memset(shaizi,0,sizeof(shaizi));
    shaizi[1]=true;
    for(int i=1;i<=maxn;i++)
    {
        if(!shaizi[i])
        {
            prin++;
            pri[prin]=i;
        }
        for(int j=1;j<=prin&&i*pri[j]<=maxn;j++)
        {
            shaizi[i*pri[j]]=true;
            if(i%pri[j]==0)break;
        }
    }
}

int main()
{
    cin>>n;
    if(n==0)
    {
        printf("0n");
        return 0;
    }
    if(!n&1)
    {
        cout<<n/2<<endl;
        return 0;
    }
    //int s=sqrt(n);
    init();
    int f=0;
    for(int i=1;i<=prin;i++)
    {
        if(n%pri[i]==0)
        {
            n-=pri[i];
            f=1;
            break;
        }
    }
    if(!f)printf("1n");
    else cout<<n/2+1<<endl;
    return 0;
}