C++ 解法, 执行用时: 151ms, 内存消耗: 15464K, 提交时间: 2022-07-22 16:07:28

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=10000009;
ll prime[N],cnt=0;
bool st[N];
void calculate_prime(){
	for(ll i=2;i<=N;i++){
		if(!st[i]) prime[cnt++]=i;
		for(ll j=0;prime[j]<=N/i;j++){
			st[i*prime[j]]=true;
			if(i%prime[j]==0)
				break;
		}
	}
}

int main(){
	calculate_prime();
	bool FFF=true;
	int n,k,m=0;
	scanf("%d%d",&n,&k);
	if(n<=2){
		cout<<0;
		return 0;
	}
	for(ll i=1;prime[i]<=n;i++){
		m++;
		if(prime[i]-prime[i-1]>k+1){
			FFF=false;
		}
	}
	if(n-prime[m]>k){
		cout<<0;return 0;
	}
	if(FFF){
		int pos,ans=0;
		while(1){
			pos=n-k;
			int prm=lower_bound(prime,prime+m,pos)-prime;
			ans++;
			if(prime[prm]<=3) break; 
			n=prime[prm]-1; 
			ans++; 
		}
		printf("%d\n",ans);
	}
	else{
		int ans=0,cnt=m;
		if(n==prime[m]){
			if(n<=prime[m-1]+k) cnt--; 
			else{
				cout<<0;
				return 0;
			}
		}
		while(1){
			if(n<=prime[cnt]+k){
				n=prime[cnt];
			}
			else break;
			ans++;
			int pos=n-k; 
			int prm=upper_bound(prime,prime+m,pos)-prime;
			n=prime[prm]-1;
			cnt=prm-1;
			ans++;
		}
		if(ans) printf("%d\n",-ans);
		else cout<<0;
	}
	return 0;
}