赞
踩
判断是否素数有3种方式:简单素性测试、埃氏筛法,欧拉筛法
举个例子:素数打表
1.从1判断到n本身
#include<iostream> #include<string.h> #include<stdio.h> #include<math.h> using namespace std; int main(){ int n; cin>>n; int a[10000]; int i,j; int q = 0; for(i = 2; i <= n; i++){ for(j = 2; j <= i; j++){ if( i%j == 0 ) break; } if( i == j ){ a[q]=i; q++; } } for(int i = 0; i < q; i++) cout << a[i] << endl; return 0; }
2.判断到根号n
#include<iostream> #include<string.h> #include<stdio.h> #include<math.h> using namespace std; int main(){ int i,j,n,x; cin>>n; int a[10000]; int q=0; for(i=2;i<=n;i++){ x=sqrt(i); for(j=2;j<=x;j++){ if(i%j==0) break; } if(j>x){ a[q]=i; q++; } } for(i=0;i<q;i++) cout<<a[i]<<endl; return 0; }
3.埃氏筛法:把不大于根号 n 的所有素数的倍数剔除,剩下的就是素数
普通筛法
出现一个数,则把以这个数为因子的数都标记为合数。
如2,所以4,6,8 10…都标记为合数
如3,所以9,12,15…都标记为合数
如4,所以16,20,24…都标记为合数
即,若i是素数,则从 j=ii 开始,把 j+i , j+2i , j+3i …都标记为合数 (因为2i , 3i,4i,…(i-1)i 分别是2,3,4,…i-1的的倍数,已经在i之前标记过,所以从j=ii开始标记)
筛法的思想是去除要求范围内所有的合数,剩下的就是素数了,而任何合数都可以表示为素数的乘积,因此如果已知一个数为素数,则它的倍数都为合数。
#include<iostream> #include<string.h> #include<stdio.h> #include<math.h> int main(){ int prime[100001]; for(int i=0;i<=100000;i++){ prime[i]=1; } for(int i=2;i<=sqrt(100000);i++){ if(prime[i]){ for(int j=i*i;j<=100000;j+=i){ prime[j]=0; } } } for(int i=2;i<=100000;i++){ if(prime[i]) cout<<a[i]<<endl; } return 0; }
4.线性筛法:筛选掉所有合数,留下质数
比一个合数数大的质数和该合数的乘积可用一个更大的合数和比其小的质数相乘得到(你从小的质数开始筛选,那么我们就可以找出)这也是if(!( i % prime[j]))break;的含义,这也是线性筛法算质数表的关键所在
#include <stdio.h> #include <string.h> #define MAXN 100000 #define MAXL 1000000 int prime[MAXN]; bool check[MAXL]; int main(void){ int n, count; while (~scanf("%d", &n)){ memset(check, 0, sizeof(check)); count = 0; for (int i = 2; i <= n; i++){ if (!check[i]) prime[count++] = i; for (int j = 0; j < count; j++){ if (i*prime[j] > MAXL) break; check[i*prime[j]] = 1; if ( (i%prime[j]) == 0 ) //关键 break; } } for (int i = 0; i < count; i++) printf("%d\n", prime[i]); } return 0; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。