质数与合数

题意：
有n个石头，FFF和GGG轮流对这堆石头进行操作，每一次可以取[1,k]个石头，但FFF取完后石头数为质数，GGG取完后石头数为合数，如果FFF赢了，则输出回合数，如果GGG赢了，则输出回合数的相反数。

注意：1既不是质数，也不是合数。
胜利者会尽可能的快点赢，输者会尽可能的慢点输。

思路：
快点赢则胜利者会尽可能的多取点，慢点输则输者会尽可能的少取点。
我们首先要知道谁赢，如果第一步都不能走则FFF输，然后如果石头数内有两质数之间相差大于k+1则FFF一定输（因为GGG取成大质数-1时FFF无法取），否则FFF一定赢（因为FFF取到小于等于3时GGG无法取）

代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll inf=1e9+7;

int pa[1000005], sum[1000005], prime[10000005], ji=0;

int main()
{
    int n, k, ans=0;
    scanf("%d%d",&n,&k);
    pa[0]=pa[1]=1;
    for(int i=2; i*i<=1000000; i++)
    {
        if(!pa[i])
        {
            for(int j=i*i; j<=1000000; j=j+i)
            {
                pa[j]=1;
            }
        }
    }
    for(int i=2;i<=1000000;i++)
    {
        if(!pa[i])
        {
            prime[ji++]=i;
        }
    }
    int flag=0, ti=-1, zui;
    for(int i=1;prime[i]<n;i++)
    {
        if(prime[i]-prime[i-1]>k+1)
        {
            flag=1;
            ti=i;
        }
        zui=i;
    }
    if(n<=2||n-prime[zui]>k)
    {
        ans=0;
    }
    else if(flag==0)
    {
        for(int i=n;;)
        {
            if(i-k<=3)
            {
                ans++;
                break;
            }
            int ki=lower_bound(prime,prime+ji,i-k)-prime;
            i=prime[ki];
            ans++;
            if(!pa[i-1])
            {
                break;
            }
            i--;
            ans++;
        }
    }
    else
    {
        for(int i=n;;)
        {
            int ki=lower_bound(prime,prime+ji,i)-prime-1;
            if(i-prime[ki]>k)
            {
                break;
            }
            i=prime[ki];
            ans--;
            if(i-k<=prime[ti]-1)
            {
                ans--;
                break;
            }
            if(!pa[i-k])
            {
                i=i-k+1;
            }
            else
            {
                i=i-k;
            }
            ans--;
        }
    }
    printf("%d\n",ans);
    return 0;
}