首页 > 其他 > 详细

快速幂与素数打表

时间:2019-07-18 22:41:57      阅读:69      评论:0      收藏:0      [点我收藏+]

素数打表 

1 2 3 4 5 6 7 8 9 10 11 12 

1 0 1 0 1 0 1 0 0  0  1    1

是素数则记录为1 ,不是素数标记为0,  素数的倍数一定是素数

 

#include<iostream>
#include<cstring>
using namespace std;
const int max=1e6;//从1到max的素数; 
typedef long long ll;
int prime[max];
int main()
{
    int n,m;
    memset(prime,0,sizeof(prime));
    int len=sqrt(max+1);//取根号 
    prime[0]=prime[1]=1;//0 he 1一定为素数 
    for(int i=2;i<len;i++)
    {
        if(prime[i])//素数标记为1,非素数标记为0;
        {
            for(int j=i+i;j<max;j+=i)
            {
                prime[j]=0;//素数的倍数一定不是素数 
            }
        }
    }
    return 0;
 } 
//快速幂
#include<iostream> #include<cstring > using namespace std; typedef long long ll; int pow(int x,int y) { int res=1; while(y>0) { if(y&1) res = res * x % 1000; x = x * x % 1000; y>>=1; } return res; } int main() { int n,m; while(cin>>n>>m) { if(n==0&&m==0) return 0; cout<<pow(n,m)<<endl; } return 0; }

 

快速幂与素数打表

原文:https://www.cnblogs.com/Accepting/p/11209715.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!