* on （CF-237C）*前缀和*二分查找 莫名眼熟的题目 。。这个类型的题好像有很多 。数据很大，枚举超时，又是用前缀和，我又没想到！！还要用二分，找最小的区间，然后循环这个大小的区间和，看看是否满足条件 。难点，二分前缀和 。
*处女座的测验（一） 积性函数！本身是因子，并且求出两者相乘数的因子个数 。哦嚯，素数打表，t()是积性函数，满足t(xy)=t(x)t(y)，要满足最后结果>10 。对于任意一个质数来说它的因子数都是只有两个1和它本身，那么两个质数相乘就是有4个，那么再让这两个质数相乘的积再相乘的话，就会一共有16个因子，所以任意的四个质数相乘的结果的因子个数都是16个，所以根据这个条件我们先筛除前4000个质数，然后首尾两两相乘就可以得到需要的2000个数了(如果不是首尾相乘而是相邻两个相乘，到后面会超过题目要求的范围) 。
积性函数：成立需要满足：xy两两互质 。
看了两个大佬的博客，终于看了这20多个素数的题目，总的来说，素数整体题目偏简单，但是要是组合着别的算法考也不是很好理解 。难点在于->超时、题目理解、算法结合 。
要讨论判断一个【1,2^31】内的数是否为素数，因为2^31太大无法打完整的表，所以我们要投巧 。
根据基本素数判别法 。打一个1~50 000的素数表，看该数字是否存在一个1~50 000的素因子，如果存在就不是素数，否则是素数 。因为任何一个非素数都可以表示为若干个素数之积 。
#define N 50001bool isprime[N];int prime[N],nprime;//1~5万素数打表void doprime(){long long i,j;nprime=0;for(i=0;i
*POJ 2689 Prime
题意：给定两个数L,R（1≤L＜R≤2 147 483 647），在[L,R]内找出相邻素数C1,C2使其距离最小，找出相邻素数C3,C4使其距离最大 。若距离相同，选最初的一组 。（R-L
思路：L和R的范围比较大，不能直接打表 。
因为正整数N是素数，当且仅当N不能被任何一个小于sqrt（N）的素数整除 。所以如果N是一个合数，那么N必然存在一个小于sqrt（N）的素数因子 。
而sqrt（2 147 483 647）
代码：（啊哈~总感觉间过好几次这个题了，可四现在才有点会，过几天可能就不能想起来这个代码了 。。但是果然吧！以前不会的早晚我都会会的！！心情不好看不进去当然是不会的啦）
#include #include #include #include using namespace std;typedef long long int64;bool isprime[1000005];int prime[50001],nprime,use[1000005];//素数打表void doprime(){long long i,j;prime[1]=2;nprime=1;for(i=1;i<50000;i+=2)isprime[i]=true;for(i=2;i<50000;i++){if(isprime[i]){prime[++nprime]=i;for(j=i*i;j<=50000;j+=i)isprime[j]=false;}}}求最大最小的区间bool solve(int64 L,int64 R,int64 &a,int64 &b,int64 &c,int64 &d){//先利用刚刚打的1~50000的表打出L-R的表int64 i,j,s;for(i=1;i=0)isprime[j-L]=false;}int np=0;//因为刚刚存的就是j-L的表，现在也要跟着一起变for(i=0;i<=R-L;i++){if(isprime[i]){//i+L才是那个素数use[np++]=i+L;}}抱歉，区间内没有素数if(np<=1)return false;//找鸭~~int dmax=-1,dmin=2147483647;for(i=0;idmax){dmax=use[i+1]-use[i];c=use[i];d=use[i+1];}}return true;}int main(){doprime();int64 a,b,c,d;int64 L,R;while(scanf("%lld%lld",&L,&R)!=EOF){if(L<=1) L++;memset(isprime,true,sizeof(isprime));if(solve(L,R,a,b,c,d))printf("%lld,%lld are closest, %lld,%lld are most distant.\n",a,b,c,d);elseprintf("There are no adjacent primes.\n");}return 0;}
*算法
1.题目：判断一个【1，2^63】内的数是否为素数
2.思路：大数判断素数，这个方法大概是那种判断成功概率极大的算法，但也不是百分白的正确率的，大数的算法永远是人们心中的痛