数论概览——素数篇

素数篇"/>

数论概览——素数篇

很久没写数论了，现在筛个素数都吃力了，写几道老题熟练一下，顺便弄下今年的模板

第一部分：关于素数

素数是数论里最重要的一种数，很多定理和性质都由素数展开。所以就有人称数论为素论，可见素数在数论中的重要性。

1.筛素数 记一下素数定理：小于N的素数的个数为f(N) 则f(N)~N/lnN,N->正无穷
【线性筛素数】【区间筛素数】
[POJ2689]=2689

/*
计算L，U区间内相邻的差最小的和差最大的两对素数
L,U可能很大，但U-L不大，二次筛素数即可，区间筛素数
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long intt;
const int MAXN2 = 1000100;
const int MAXN = 47000;
int noprime[MAXN],pcnt,p[MAXN];
inline void getprime(){pcnt = 0;memset(noprime,0,sizeof(noprime));noprime[0] = noprime[1] = 1;for(int i = 2; i < MAXN; ++i){if(!noprime[i])p[pcnt++] = i;for(int j = 0; j < pcnt && i*p[j] < MAXN; ++j){noprime[i*p[j]] = 1;if(i%p[j] == 0)break;}}
}intt p2[MAXN2];
int pcnt2,noprime2[MAXN2];
inline void getprime2(intt L,intt U){pcnt2 = 0;if(U < MAXN){int s = 0;while (p[s] < L)s++;for(intt i = s; p[i] <= U; ++i)p2[pcnt2++] = p[i];return;}for(int i = 0; i <= U-L; ++i)noprime2[i] = 0;for(int i = 0; i < pcnt && p[i]*p[i] <= U; ++i){intt st = L/p[i];if(L%p[i] == 0)st = L;else st = p[i]*(st+1);    for(intt j = st; j <= U; j += p[i])noprime2[j-L] = 1;}if(L == 1)noprime2[0] = 1;for(intt i = L; i <= U; ++i){if(!noprime2[i-L])p2[pcnt2++] = i;}
}
int main(){intt L,U;getprime();while (scanf("%lld%lld",&L,&U) != EOF){getprime2(L,U);if(pcnt2 < 2){puts("There are no adjacent primes.");continue;}intt ansmax = 0,ima = 0;intt ansmin = U,imi = 0;for(int i = 1; i < pcnt2; ++i){if(ansmax < p2[i] - p2[i-1]){ansmax = p2[i] - p2[i-1];ima = i;}if(ansmin > p2[i] - p2[i-1]){ansmin = p2[i] - p2[i-1];imi = i;}}printf("%lld,%lld are closest, %lld,%lld are most distant.\n",p2[imi-1],p2[imi],p2[ima-1],p2[ima]);}return 0;
}

【质因子分解】【n！的质因子分解】
[POJ2649]=2649

/*
*两个数n和m，问n！能否整除m
*先对m质因数分解，然后判断n!的m中的质因子的数目是不是大于m中该质因子的个数
*这里有个结论：n!中因子p的个数可以这样求：
*int t = n,sum = 0;
*while ( t > 0 ) {
*     sum += t / p;
*     t /= p;
*}
*sum即为n!中因子p的个数
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;const int MAXN = 65537;int noprime[MAXN],pcnt,p[MAXN/2];
inline void getprime(){pcnt = 0;memset(noprime,0,sizeof(noprime));noprime[0] = noprime[1] = 1;for(int i = 2; i < MAXN; ++i){if(!noprime[i])p[pcnt++] = i;for(int j = 0; j < pcnt && i*p[j] < MAXN; ++j){noprime[i*p[j]] = 1;if(i%p[j] == 0)break;}}
}int nump[MAXN/2],yinzi[MAXN/2];
int n,m,top;
inline void cal(int t){memset(nump,0,sizeof(nump));top = -1;int tmp = t;for(int i = 0;i < pcnt && p[i] <= tmp; ++i){if(t % p[i] == 0){yinzi[++top] = p[i];while (t % p[i] == 0){nump[top] ++;t /= p[i];}}if(t == 1)break;}if(t > 1){yinzi[++top] = t;nump[top] ++;}}int main(){getprime();while (scanf("%d%d",&n,&m) != EOF){if(m == 0){printf("%d does not divide %d!\n", m, n);continue;}cal(m);bool ok = 1;for(int i = 0; i <= top; ++i){if(yinzi[i] > n){ok = 0;break;}int t = n,sum = 0;while (t > 0){sum += t/yinzi[i];t /= yinzi[i];if(sum >= nump[i])break;}if(sum < nump[i]){ok = 0;break;}}if(ok)printf("%d divides %d!\n",m,n);else printf("%d does not divide %d!\n",m,n);}return 0;
}

/*
质因子分解的用途
对求数字的因子加速,即任何的n的素因子Pi都有Pi|n,这是显然的.于是可以利用这个特点，在得到素因子的种类和个数以后采取枚举的做法来得到所有的因子(一般用dfs递归实现)
*/
2.素数测试
【米勒拉宾素数测试+RHO大数分解】
a)最简单的是(2..sqrt(n))试除判断是否素数 复杂度O(sqrt(N))
b)米勒拉宾素数测试+RHO大数分解 复杂度O(logN)

Miller - Rabin素数测试的伪码
Input: n > 2, an odd integer to be tested for primality; k, a parameter that determines the accuracy of the test  
Output: composite if n is composite, otherwise probably prime  
write n − 1 as 2^s·d with d odd by factoring powers of 2 from n − 1  
LOOP: repeat k times:  pick a randomly in the range [2, n − 2]  x ← a^d mod n  if x = 1 or x = n − 1 then do next LOOP  for r = 1 .. s − 1  x ← x^2 mod n  if x = 1 then return composite  if x = n − 1 then do next LOOP  return composite  
return probably prime 

[POJ1811]模板题，直接上代码

#include <cstdio>
#include <cstring>
#include <ctime>
#include <algorithm>
using namespace std;
typedef long long bint;
const int TIME = 8;//测试次数，8~10够了
int factor[100],fac_top = -1;//计算两个数的gcd
inline bint gcd(bint small,bint big){while(small){swap(small,big);small%=big;}return big > 0 ? big : -big;
}//ret = (a*b)%n (n<2^62)
inline bint muti_mod(bint a,bint b,bint n){bint exp = a%n, res = 0;while(b){if(b&1){res += exp;if(res>n) res -= n;}exp <<= 1;if(exp>n) exp -= n;b>>=1;}return res;
}// ret = (a^b)%n
inline bint mod_exp(bint a,bint p,bint m){bint exp=a%m, res=1; //  while(p>1){if(p&1)//res=muti_mod(res,exp,m);exp = muti_mod(exp,exp,m);p>>=1;}return muti_mod(res,exp,m);
}//miller-rabin法测试素数, time 测试次数O（lonN）
inline bool miller_rabin(bint n, int times){if(n==2)return 1;if(n<2||!(n&1))return 0;bint a, u=n-1, x, y;int t=0;while(u%2==0){t++;u/=2;}srand(time(0));for(int i=0;i<times;i++){a = rand() % (n-1) + 1;x = mod_exp(a, u, n);for(int j=0;j<t;j++){y = muti_mod(x, x, n);if ( y == 1 && x != 1 && x != n-1 )return false; //must notx = y;}if( y!=1) return false;}return true;
}inline bint pollard_rho(bint n,int c){//找出一个因子bint x,y,d,i = 1,k = 2;srand(time(0));x = rand()%(n-1)+1;y = x;while(true) {i++;x = (muti_mod(x,x,n) + c) % n;d = gcd(y-x, n);if(1 < d && d < n)return d;if( y == x)       return n;if(i == k) {y = x;k <<= 1;}}
}inline void findFactor(bint n,int k){//二分找出所有质因子，存入factor,if(n==1)return;if(miller_rabin(n, TIME)){factor[++fac_top] = n;return;}bint p = n;while(p >= n)p = pollard_rho(p,k--);//k值变化，防止死循环findFactor(p,k);findFactor(n/p,k);
}int main(){bint cas,n,min;scanf("%lld",&cas);while(cas--){scanf("%lld",&n);fac_top = min = -1;if(miller_rabin(n,TIME)) puts("Prime");else{findFactor(n,1000);//factor保存该数的所有质因子，0..fac_topfor(int i = 0;i <= fac_top;i++){if(min < 0 || factor[i] < min)min = factor[i];}printf("%lld\n",min);}}return 0;
}

3.欧拉函数
对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目
显然对素数n,phi(n)=n-1
通式：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有质因数，x是不为0的整数。φ(1)=1（唯一和1互质的数就是1本身）
很简单，就不写代码什么的了