【数论基础】判断素数、埃拉托色尼筛选法、欧几里得算法、反复平方法
目录
筛选素数
快速筛选素数：埃拉托色尼筛选法
只有一行的算法：欧几里得算法求解最大公约数
求幂乘：反复平法法
筛选素数小学的知识点，不解释了；
bool isPrime(int d){//判断是否是素数
if(d==2)
return true;
if(d<2||d%2==0)
return false;
int i=3;
while(i<=sqrt(d)){//注意开方,减少无所谓的运算
if(d%i==0)
return false;
i+=2;
}
return true;
}
快速筛选素数：埃拉托色尼筛选法
如果要筛选1~n范围内的素数，最大限度减少运算量
列举大于等于2的整数
留下最小的整数2，删除所有2的倍数
在剩下的整数中留下最小的3，删除所有3的倍数
在剩下的整数中留下最小的5，删除所有5的倍数
剩下的同理，留下仍未被删除的最小整数，删除该整数的倍数，一直循环到结束
//埃拉托色尼筛选法
#include
#include
using namespace std;
bool prime[1000];
void eratos(int n){
for(int i=0;i<=n;i++)//列举所有整数作为候选
prime[i]=true;
//删除0和1
prime[0]=prime[1]=false;
//留下i,删除i的倍数
for(int i=2;i<=sqrt(n);i++){
if(prime[i]){
int j=i+i;
while(j<=n){
prime[j]=false;
j+=i;
}
}
}
}
int main(){
int n;
eratos(n);
for(int i=1;i<=n;i++)
if(prime[i])
cout<<i<<" ";
return 0;
}
只有一行的算法：欧几里得算法求解最大公约数
核心思想：当x大于等于y时，gcd(x,y)等于gcd(y,x除以y之后的余数)
int gcd(int x,int y){
return y?gcd(y,x%y):x;
}
换用好理解的：
int gcd(int x,int y){
if(x0){
int r = x%y;
x=y;
y=r;
}
return x;
}
求幂乘：反复平法法
博客里不好编辑公式，就不解释了（其实就是懒。。。）
//反复平方法
#include
#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll modpow(ull x,ull n){
ull res = 1;
while(n>0){
if(n&1)
res = res*x;
x = x*x;
n>>=1;
}
return res;
}
int main(){
int m,n;
cin>>m>>n;
cout<<modpow(m,n)<<endl;
return 0;
}
作者：沉迷单车的追风少年
相关文章
Serafina
2021-03-06
Odetta
2020-10-12
Serwa
2020-03-20
Genet
2020-12-30
Valora
2021-02-16
Hester
2023-07-22
Grace
2023-07-22
Vanna
2023-07-22
Peony
2023-07-22
Dorothy
2023-07-22
Dulcea
2023-07-22
Zandra
2023-07-22
Serafina
2023-07-24
Kathy
2023-08-08
Olivia
2023-08-08
Elina
2023-08-08
Jacinthe
2023-08-08
Viridis
2023-08-08
Hana
2023-08-08