当前位置:首页 > 编程入门 > 计算机知识 > 素数问题及快速幂

素数问题及快速幂
栏目分类:计算机知识发布日期:2020-01-30浏览次数:

素数问题及快速幂 通过近几天的训练,确实收获很多,之前很简单的素数问题也学到了更省时的方法。 这是之前大多数人用的方法: int pd ( int n ) { for ( int i = 2 ; i n ; i ++) if ( n % i == 0 ) return 0 ; return 1 ; } 更加节约时间的方法,函数只需要

素数问题及快速幂

通过近几天的训练,确实收获很多,之前很简单的素数问题也学到了更省时的方法。
这是之前大多数人用的方法:

  1. int pd(int n)
  2. {
  3. for(int i=2;i<n;i++)
  4. if(n%i==0)
  5. return 0;
  6. return 1;
  7. }

更加节约时间的方法,函数只需要调用一次。 完整代码如下:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int s[10000];
  4. void pd(int n)
  5. {
  6. for (int i = 2; i <= sqrt(n); i++)
  7. if (s[i] == 0)
  8. for (int k = i * i; k <= n; k+=i)
  9. s[k] = 1;
  10. }
  11. int main()
  12. {
  13. int n;
  14. cin >> n;
  15. pd(n);
  16. for (int i = 2; i <= n; i++)
  17. if (s[i] == 0)
  18. cout << i << endl;
  19. }

以及快速幂的方法,比如求(n^m)%mod 基本算法:

  1. int main()
  2. {
  3. int n,m,mod,ans=1;
  4. cin>>n>>m>>mod;
  5. while(m--)
  6. ans=ans*n%mod;
  7. cout<<ans%mod<<endl;
  8. }

如果是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很大的时候可以节约很多时间。 快速幂代码如下:

  1. int main()
  2. {
  3. int n,m,mod,ans=1;
  4. cin>>n>>m>>mod;
  5. while(m)
  6. {
  7. if(m%2!=0)
  8. ans=ans*n%mod;
  9. n=n*n%mod;
  10. m/=2;
  11. }
  12. cout<<ans%mod<<endl;
  13. }



 

相关热词:

     
编程入门 编程教程 编程资源 编程问答