| 求1~n之间的素数 |
| 难度级别：A； 运行时间限制：1000ms； 运行空间限制：256000KB； 代码长度限制：2000000B |
|
试题描述
|
|
素数是大于1，且除1和本身以外不能被其他整数所整除的数。要求输出1~n之间的素数。
|
|
输入
|
|
正整数n
|
|
输出
|
|
1~n之间的所有素数，包括n，数字之间用一个空格隔开，第一个数字前不能有空格。
|
|
输入示例
|
|
10
|
|
输出示例
|
|
2 3 5 7
|
|
其他说明
|
|
n是大于1且不大于100的正整数
|
题解：可以练习一下MR（都不会打了）
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<algorithm> 5 #include<queue> 6 #include<cstring> 7 #include<ctime> 8 #define PAU putchar(' ') 9 #define ENT putchar(' ') 10 using namespace std; 11 const int Safe=3; 12 int gcd(int a,int b){return !b?a:gcd(b,a%b);} 13 int mul(int a,int b,int p){ 14 int tmp=(a*b-(int)((double)a/p*b+1e-8)*p); 15 return tmp<0?tmp+p:tmp; 16 } 17 int pow(int a,int b,int p){ 18 int ans=1;a%=p; 19 for(int i=b;i;i>>=1,a=mul(a,a,p)) 20 if(i&1)ans=mul(ans,a,p); 21 return ans; 22 } 23 bool check(int a,int n,int r,int s){ 24 int ans=pow(a,r,n),p=ans; 25 for(int i=1;i<=s;i++){ 26 ans=mul(ans,ans,n); 27 if(ans==1&&p!=1&&p!=n-1) return true; 28 p=ans; 29 } if(ans!=1)return true;return false; 30 } 31 bool MR(int n){ 32 if(n<=1) return false; 33 if(n==2) return true; 34 if(!(n&1)) return false; 35 int r=n-1,s=0; 36 while(!(r&1)) r>>=1,s++; 37 for(int i=0;i<Safe;i++) 38 if(check(rand()%(n-1)+1,n,r,s)) return false; 39 return true; 40 } 41 inline int read(){ 42 int x=0,sig=1;char ch=getchar(); 43 while(!isdigit(ch)){if(ch=='-')sig=-1;ch=getchar();} 44 while(isdigit(ch))x=10*x+ch-'0',ch=getchar(); 45 return x*=sig; 46 } 47 inline void write(int x){ 48 if(x==0){putchar('0');return;}if(x<0)putchar('-'),x=-x; 49 int len=0,buf[15];while(x)buf[len++]=x%10,x/=10; 50 for(int i=len-1;i>=0;i--)putchar(buf[i]+'0');return; 51 } 52 bool first=true; 53 void init(){ 54 srand(time(0)); 55 int n=read(); 56 for(int i=2;i<=n;i++){ 57 if(MR(i)){ 58 if(first) first=false; 59 else PAU; 60 printf("%d",i); 61 } 62 } 63 return; 64 } 65 void work(){ 66 return; 67 } 68 void print(){ 69 return; 70 } 71 int main(){init();work();print();return 0;}