素数问题及快速幂

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

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. }