初等数论c++

　　备注：纯手写代码，注释。

　　数论

　　1、素数

　　（1）暴力求解法

　　根据素数的概念，没有1和其本身没有其他正因数的数。 所以只需枚举比这个数小的数，看能整除即可； C++代码：

　　#includeiostream

　　#includecstdio

　　#includecmath

　　using namespace std;

　　bool determine(int number)

　　{

　　if(n=2)return false;

　　if(!n%2)return false;

　　for(int i=3;i=ceil(sqrt(number));i+=2)

　　//去掉了偶数的判断，效率提高一倍

　　/*如果number整除以i，那么会得到两个的因数，

　　而较小的那个因数不会超过number的二分之一次方；

　　所以只需判断到number的平方根向上取整即可； */

　　if(number%i);

　　else return false;

　　return true;

　　}

　　int main()

　　{

　　int sum;

　　cin

　　if(determine(sum))

　　coutYES!

　　else coutNO!

　　return 0;

　　}

　　时间复杂度：o(sqrt(n)/2);

　　空间复杂度：几乎没有；

　　（2）一般线性筛法：

　　因为任何一个合数都能分解成几个素数相乘的形式；

　　所以可以做一个表，首先把2设为质数，然后将2的倍数设为合数，剩下的数就是新得到的质数，然后重复这个过程，直到筛到合适的范围即可；

　　但是这个算法有缺陷：

　　1、 同一个数可能被筛多次，这就产生了多余的步骤。

　　2、 占用空间很大，如果使用bool数组的话，只能筛到1e9；

　　3、 从1-n筛，不能从m-n开始筛；

　　C++代码：

　　#includecstring

　　#includecmath

　　#includeiostream

　　using namespace std;

　　bool s[1000000000];

　　int m,n;

　　int main()

　　{

　　cinm

　　memset(s,true,n);

　　s[0]=s[1]=0;

　　//输出M—N之间所有素数；

　　for(int i=2;i=ceil(sqrt(n));++i)

　　if(s[i])

　　{

　　for(int j=i;j++j)

　　if(s[i*j])

　　s[i*j]=false;

　　}

　　for(int i=m;i++i)

　　if(s[i])

　　couti

　　return 0;

　　}

　　时间复杂度：o(n*loglogn);

　　空间复杂度：很大！注意数据大的话可能会爆空间；

　　（3）线性筛法求素数

　　这个占空间就更大了，需要使用一个bool数组和int数组 而亲身试验得到int数组最多开到1e8……

　　很无语，快确实是快了，但是测试数据一大，爆空间就更容易了； #includeiostream

　　#includecstdio

　　#includecmath

　　using namespace std;

　　int m,n,sum;

　　bool inp[1000000000];

　　int s[100000000]={0,0};

　　int main()

　　{

　　cinm

　　for(int i=2;i++i)

　　{

　　if(!inp[i])

　　s[sum++]=i;

　　for(int j=0;ji*s[j]++j) {

　　inp[i*s[j]]=true;

　　if(!(i*s[j]))

　　break;

　　}

　　}

　　for(int i=m;i++i)

　　if(!inp[i])

　　couti

　　return 0;

　　}

　　2、唯一分解定理

　　任何数都可以被唯一的分解成多个素数之积 例如：456=2*2*2*3*19；

　　C++代码：

　　#includecstring

　　#includecmath

　　#includeiostream

　　#includealgorithm

　　#includecstdlib

　　using namespace std;

　　bool s[1000000];

　　int m,n,sum=0,num;

　　int Prime[1212121];

　　int zhi[1500];

　　void Primes()

　　{

　　for(int i=1;i++i) s[i]=true;

　　s[0]=s[1]=0;

　　for(int i=2;i++i) if(s[i])

　　{

　　Prime[++sum]=i;

　　for(int j=i;j++j) if(s[i*j])

　　s[i*j]=false; }

　　}

　　int main()

　　{

　　int flag=0;

　　cin

　　int number=num;

　　Primes();

　　if(s[num])

　　{

　　coutnum'=' return 0;

　　}

　　coutnum=str.chu(); while(num1)

　　for(int i=1;num=sum;++i) if(!(num%Prime[i])) {

　　zhi[++flag]=Prime[i]; num/=Prime[i]; }

　　sort(zhi+1,zhi+flag+1);

　　coutzhi[1];

　　for(int i=2;i++i)

　　cout*

　　return 0;

　　}

　　首先做一个质数表，并把质数存到数组里，然后用数模每个素数，如果为0则记录素数，最后排个序输出；

　　4、 欧拉函数

　　欧拉函数φ（n）为不大于n的与n互素的数的个数；

　　A与B互素，表示a与b的最大公约数为1，即（a，b）=1； 欧拉函数的符号φ读作fhi，在搜狗的特殊符号里可以找到；

　　，其中pi为x的质因数，其中

　　φ(1)=1（唯一与1互质的数是1本身） 设n为正整数，以 φ(n)表示不超过n且与n互素的正整数的个数，称为n的欧拉函数值

　　φ：N→N，n→φ(n)称为欧拉函数。

　　几个性质（来自百度百科）

　　1、若n是质数p的k

　　次幂，

　　的倍数外，其他数都跟n互质。

　　2、欧拉函数是积性函数——若m,n互质，

　　3、特殊性质：当n为奇数时，

　　4、若n为质数则 ，因为除了p , 证明与上述类似。

　　5、设p是素数，a

　　是一个正整数，那么 C++实现：

　　#includecstring

　　#includecmath

　　#includeiostream

　　#includealgorithm

　　#includecstdlib

　　using namespace std;

　　bool s[1000000];

　　int m,n,sum=0,num;

　　int Prime[1212121];

　　int zhi[1500];

　　bool asd[1500];

　　int phi(int n)

　　{

　　int i,rea=n;

　　for(i=2;i*ii++)

　　{

　　if(n%i==0)

　　{

　　rea=rea-rea/i;

　　while(n%i==0) n/=i;

　　}

　　}

　　if(n1)

　　rea=rea-rea/n; return rea;

　　}

　　void Primes()

　　{

　　for(int i=1;i++i) s[i]=true;

　　s[0]=s[1]=0;

　　for(int i=2;i++i) if(s[i])

　　{

　　Prime[++sum]=i;

　　for(int j=i;j++j) if(s[i*j])

　　s[i*j]=false; }

　　}

　　int main()

　　{

　　int flag=0;

　　cin

　　int number=num;

　　Primes();

　　if(num==1||!num)

　　{

　　coutfhinumber)= cout

　　return 0;

　　}

　　if(s[num])

　　{

　　coutfhinumber)=number-1; return 0;

　　}

　　while(num1)

　　for(int i=1;num=sum;++i)

　　if(!(num%Prime[i]))

　　{

　　zhi[++flag]=Prime[i];

　　num/=Prime[i];

　　}

　　int fenzi=1,fenmu=1;

　　sort(zhi+1,zhi+flag+1);

　　for(int i=1;i++i)

　　if(!asd[zhi[i]])

　　{

　　asd[zhi[i]]=true;

　　fenzi*=zhi[i]-1;

　　fenmu*=zhi[i];

　　}

　　coutfhi(number)=number/fenmu*fenzi; //coutfhi(number)=fhi(number); /*这是另一种求欧拉函数值的方法*/

　　return 0;

　　}

　　5、欧几里得算法

　　辗转相除法，根据公式(a,b)=(b,r)

　　其中r为a%b，即a/b；

　　C++代码：

　　（1）递归

　　#includeiostream

　　#includecstdio

　　using namespace std;

　　int GCD(int a,int b) {

　　if(a%b)

　　return GCD(b,a%b); else return b; }

　　int main()

　　{

　　int a,b;

　　cina

　　coutGCD(a,b); return 0;

　　}

　　（2）递推

　　#includeiostream using namespace std; int main()

　　{

　　int a,b,r;

　　cina

　　r=m%n;

　　while(r!=0)

　　{

　　a=b;

　　b=r;

　　r=m%n;

　　}

　　cout

　　return 0;

　　}

　　6、扩展欧几里得 扩展欧几里得又称斐蜀定理，对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得 gcd（a，b）=ax+by；

　　求同余方程

　　#includecstdio

　　void exgcb(int a,int b,int x,int y)

　　{

　　if(!b)

　　{

　　x=1;y=0;

　　return;

　　}

　　int q=a/b;

　　int r=a%b; exgcb(b,r,y,x);

　　y-=q*x;

　　}

　　int main()

　　{

　　int x,y;

　　int a,b;

　　scanf(%d %da,

　　exgcb(a,b,x,y);

　　while(x0)

　　x+=b;

　　printf(%d

　　return 0;

　　}

　　求乘法逆元

　　#includecstdio

　　void exgcb(int a,int b,int x,int y) {

　　if(!b)

　　{

　　x=1;y=0;

　　return;

　　}

　　int q=a/b;

　　int r=a%b;

　　exgcb(b,r,y,x);

　　y-=q*x;

　　}

　　int Multiplicative inverse(int a,int b) {

　　int x,y;

　　int gcb=GCD(a,b,x,y);

　　if(1%gcb)return -1;

　　x*=1%gcb;

　　b=abs(b);

　　int answer=x%b;

　　while(answer=0)

　　answer+=b;

　　return answer;

　　}

　　int main()

　　{

　　int x,y;

　　int a,b;

　　scanf(%d %da,

　　exgcb(a,b,x,y);

　　while(x0)

　　x+=b;

　　printf(%dn

　　coutMultiplicative inverse(a,b); return 0;

　　}

　　求线性方程ax+by=c

　　这个方程等同于ax≡c（mod b） 所以