初等数论c++

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

数论

1、素数

（1）暴力求解法

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

C++代码：

#include

#include

#include

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>>sum;

if(determine(sum))

cout<<"YES!";

else cout<<"NO!";

return 0;

}

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

空间复杂度：几乎没有；

（2）一般线性筛法：

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

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

适的范围即可；

但是这个算法有缺陷：

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

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

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

C++代码：

#include

#include

#include

using namespace std;

bool s[1000000000];

int m,n;

int main()

{

cin>>m>>n;

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<=n;++j)

if(s[i*j])

s[i*j]=false;

}

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

if(s[i])

cout<

return 0;

}

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

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

（3）线性筛法求素数

这个占空间就更大了，需要使用一个bool数组和int数组

而亲身试验得到int数组最多开到1e8……

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

#include

#include

using namespace std;

int m,n,sum;

bool inp[1000000000];

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

int main()

{

cin>>m>>n;

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

{

if(!inp[i])

s[sum++]=i;

for(int j=0;j

{

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

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

break;

}

}

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

if(!inp[i])

cout<

return 0;

}

2、唯一分解定理

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

C++代码：

#include

#include

#include

#include

#include

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<=num;++i)

s[i]=true;

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

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

if(s[i])

{

Prime[++sum]=i;

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