外贸营销网站建设公司排名,企业名录app哪个好,合肥网络公司行情,品牌营销增长公司哪家好From: http://blog.csdn.net/dinosoft/article/details/5829550 素数总是一个比较常涉及到的内容#xff0c;掌握求素数的方法是一项基本功。 基本原则就是题目如果只需要判断少量数字是否为素数#xff0c;直接枚举因子2 。。N^(0.5) #xff0c;看看能否整除N。 如果需要…From: http://blog.csdn.net/dinosoft/article/details/5829550 素数总是一个比较常涉及到的内容掌握求素数的方法是一项基本功。 基本原则就是题目如果只需要判断少量数字是否为素数直接枚举因子2 。。N^(0.5) 看看能否整除N。 如果需要判断的次数较多则先用下面介绍的办法预处理。 一般的线性筛法 首先先介绍一般的线性筛法求素数 [cpp] view plaincopyprint? void make_prime() { memset(prime, 1, sizeof(prime)); prime[0]false; prime[1]false; int N31700; for (int i2; iN; i) if (prime[i]) { primes[cnt ]i; for (int ki*i; kN; ki) prime[k]false; } return; } 这种方法比较好理解初始时假设全部都是素数当找到一个素数时显然这个素数乘上另外一个数之后都是合数(注意上面的 i*i , 比 i*2 要快点 )把这些合数都筛掉即算法名字的由来。 但仔细分析能发现这种方法会造成重复筛除合数影响效率。比如10在i2的时候k2*15筛了一次在i5k5*6 的时候又筛了一次。所以也就有了快速线性筛法。 快速线性筛法 快速线性筛法没有冗余不会重复筛除一个数所以“几乎”是线性的虽然从代码上分析时间复杂度并不是O(n)。先上代码 [cpp] view plaincopyprint? #includeiostream using namespace std; const long N 200000; long prime[N] {0},num_prime 0; int isNotPrime[N] {1, 1}; int main() { for(long i 2 ; i N ; i ) { if(! isNotPrime[i]) prime[num_prime ]i; //关键处1 for(long j 0 ; j num_prime i * prime[j] N ; j ) { isNotPrime[i * prime[j]] 1; if( !(i % prime[j] ) ) //关键处2 break; } } return 0; } 首先先明确一个条件任何合数都能表示成一系列素数的积。 不管 i 是否是素数都会执行到“关键处1” ①如果 i 都是是素数的话那简单一个大的素数 i 乘以不大于 i 的素数这样筛除的数跟之前的是不会重复的。筛出的数都是 Np1*p2的形式, p1p2之间不相等 ②如果 i 是合数此时 i 可以表示成递增素数相乘 ip1*p2*...*pn, pi都是素数2in pipj ( ij ) p1是最小的系数。 根据“关键处2”的定义当p1prime[j] 的时候筛除就终止了也就是说只能筛出不大于p1的质数*i。 我们可以直观地举个例子。i2*3*5 此时能筛除 2*i ,不能筛除 3*i 如果能筛除3*i 的话当 i 等于 i3*3*5 时筛除2*i 就和前面重复了。 需要证明的东西 一个数会不会被重复筛除。合数肯定会被干掉。 根据上面红字的条件现在分析一个数会不会被重复筛除。 设这个数为 xp1*p2*...*pn, pi都是素数1in) , pipj ( ij ) 当 i 2 时就是上面①的情况 当 i 2 时 就是上面②的情况 对于 i 第一个能满足筛除 x 的数 y 必然为 yp2*p3...*pnp2可以与p1相等或不等而且满足条件的 y 有且只有一个。所以不会重复删除。 证明合数肯定会被干掉 用归纳法吧。 类比一个模型比如说我们要找出 n 中2个不同的数的所有组合 { i , j } 1in, 1jn, 我们会这么写 for (i1; in; i ) for (ji1; jn; j) { / } 我们取 ji1 便能保证组合不会重复。快速筛法大概也是这个道理不过这里比较难理解没那么直观。 1楼提供的方法我整理下 //偶数显然不行所以先去掉偶数。可以看作上面第一种的优化吧。 //不过这种方法不太直观不太好理解。 [cpp] view plaincopyprint? 我推荐这个算法 易于理解。 只算奇数部分时空效率都还不错 halfSIZE/2; int sn (int) sqrt(SIZE); for (i 0; i half; i) p[i] true;// 初始化全部奇数为素数。p[0]对应3即p[i]对应2*i3 for (i 0; i sn; i) { if(p[i])//如果 ii3 是素数 { for(kii3, jk*iki; j half; jk) // 筛法起点是 p[i]所对应素数的平方 k^2 // k^2在 p 中的位置是 k*iki // 下标 i k*iki //对应数值 kii3 k^2 p[j]false; } } //素数都存放在 p 数组中p[i]true代表 ii2 是素数。 //举例3是素数按3*3,3*5,3*7...的次序筛选因为只保存奇数所以不用删3*43*6.... 扩展阅读 打印质数的各种算法 http://coolshell.cn/articles/3738.html 里面有个用C模板实现的纯属开阔眼界不怎么实用。检查素数的正则表达式 http://coolshell.cn/articles/2704.html 数字n用 1111。。1 n个1表示纯属坑爹。 以上完整源码(a.cpp)
/*
功能: 求[0, 20000)间的所有素数, 假设内存空间足够
环境: Linux C
编译: g -o a a.cpp -Wall -Os
总结: 这两种算法在性能上差距不是很大, 当N个数较少时, 还是一般线性筛选法速度更快,
但是当N较大时, 快速线性筛选法的优势更加明显
*/
#include stdio.h
#include string.h
#define N 20000
// 一般线性筛选法: 会出现重复筛选同一个数
void make_prime(int primes[], int cnt)
{
bool bPrime[N]; // 质数标志数组
cnt 0; // 素数个数
memset(bPrime, true, sizeof(bPrime));// 假设全是素数
bPrime[0] false; // 0: 非素数
bPrime[1] false; // 1: 非素数
for (int i 2; i N; i)
{
if (bPrime[i]) // i是素数
{
primes[cnt] i; // 将素数i保存到bPrimes[]中
// 作筛选: i的倍数都不是素数
for (int k i * i; k N; k i) // 将素数i的倍数全置为非素数标志
bPrime[k] false;
}
}
}
// 快速线性筛选法: 不会出现重复筛选同一个数
void getPrimes(int primes[], int cnt)
{
bool bPrime[N]; // 素数标志数组
cnt 0; // 素数个数
memset(bPrime, true, sizeof(bPrime)); // 假设全部为素数
bPrime[0] false; // 0: 非素数
bPrime[1] false; // 1: 非素数
for(int i 2; i N; i)
{
if(bPrime[i]) // i是素数
primes[cnt] i; // 保存素数i
// 作筛选: i与素数的乘积都不是素数
for(int j 0; j cnt i * primes[j] N; j)
{
bPrime[i * primes[j]] false; // 置非素数标志
if(i % primes[j] 0) // i为素数的倍数
break;
}
}
}
int main()
{
int primes[N]; // 保存所有素数
int cnt 0; // 素数个数
#if 1
make_prime(primes, cnt); // 调用一般线性筛选法
#else
getPrimes(primes, cnt); // 调用快速线性筛选法
#endif
for(int i 0; i cnt; i)
printf(primes[%d] %d\n, i, primes[i]);
printf(\n素数个数cnt%d\n, cnt);
return 0;
}
