素数问题及快速幂
栏目分类:计算机知识 发布日期:2020-01-30 浏览次数:次
素数问题及快速幂
通过近几天的训练,确实收获很多,之前很简单的素数问题也学到了更省时的方法。
这是之前大多数人用的方法:
-
int pd(int n)
-
{
-
for(int i=2;i<n;i++)
-
if(n%i==0)
-
return 0;
-
return 1;
-
}
更加节约时间的方法,函数只需要调用一次。 完整代码如下:
-
#include<bits/stdc++.h>
-
using namespace std;
-
int s[10000];
-
void pd(int n)
-
{
-
for (int i = 2; i <= sqrt(n); i++)
-
if (s[i] == 0)
-
for (int k = i * i; k <= n; k+=i)
-
s[k] = 1;
-
}
-
int main()
-
{
-
int n;
-
cin >> n;
-
pd(n);
-
for (int i = 2; i <= n; i++)
-
if (s[i] == 0)
-
cout << i << endl;
-
}
以及快速幂的方法,比如求(n^m)%mod 基本算法:
-
int main()
-
{
-
int n,m,mod,ans=1;
-
cin>>n>>m>>mod;
-
while(m--)
-
ans=ans*n%mod;
-
cout<<ans%mod<<endl;
-
}
如果是2^10,这个算法要算出答案要进行10次运算。 快速幂的方法用数学来解释2^10=(2×2)^5=4^5=4^4×4=(4×4)^2×4=16×16×4=1024; 这样计算的话只需要进行2×2、4×4、16×16、256×4共4次运算,当m很大的时候可以节约很多时间。 快速幂代码如下:
-
int main()
-
{
-
int n,m,mod,ans=1;
-
cin>>n>>m>>mod;
-
while(m)
-
{
-
if(m%2!=0)
-
ans=ans*n%mod;
-
n=n*n%mod;
-
m/=2;
-
}
-
cout<<ans%mod<<endl;
-
}
本文由IT教学网整理发布,转载请注明出处:http://www.itjx.com/rumen/jisuanji/566.html