数字游戏[线性筛]

数字游戏[线性筛]

alice 和 bob 又在玩一个游戏。他们从一个数字 X0>=3,开始，期望到很大的数字。游戏是这样的：

alice 先走，然后轮流。在第 i 个回合中，轮到的玩家找一个小于当前数字的素数， 然后选择大于当前数字且是找的素数的倍数。即选择的素数 P=Xi-1,Xi 是 P 的倍数，注意如果 P 是 Xi-1 的约数，那么数字不会变。

L 知道了他们两轮后的状态，现在给你一个 X2 表示两轮后选择的数字，请你确定最小的起始数字 X0。特别提醒，玩家不一定每一步选择是最聪明的，你应该考虑所有可能的情况。

【输入】

输入一个整数 X2，保证 X2 是合数

【输出】

输出一个整数 X0

【输入样例 1】14

【输出样例 1】6

【样例解释】

X0=6,

第一轮：alice 选择素数 5，并决定这轮数字X1=10

第一轮：BOB 选择素数 7，并决定这轮数字 X2=14

分析

推一下，我们发现，需要求每个数的最大z质约数

void pre(int n){ for(int i=2;i<=n;i++){ if(isp[i]==0){ prim[++cnt]=i;//质数 p[i]=i; //最大质因子 } for(int j=1;j<=cnt&&prim[j]*i<=n;j++){//筛 i*比i小的质数 ->i是最大因子 isp[prim[j] * i]=1; p[prim[j] * i]=p[i];//最大质因子，每个数是由最大因子筛选出 /*一个数的最大质因子是它的最大因子的最大质因子 这个break保证了合数只被最小质约数访问到。 比如40=2*20=4*10=5*8，只有i=20时，才会在prim[j]=2的时候被访问到。 当i=10时，在prim[j]=2时就已经被break了；同样的，i=8时，在prim[j]也已经break */ if(i%prim[j]==0)break; } }}

线性筛一定要会，处理质数的利器。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。