搭建一个网站的基本流程,淘客网站建设收费吗,怎么网上推广自己的产品,动漫设计需要学什么ACM数论——素数 素数定义#xff1a; 质数#xff08;prime number#xff09;又称素数#xff0c;有无限个。质数定义为在大于1的自然数中#xff0c;除了1和它本身以外不再有其他因数#xff0c;这样的数称为质数。例 子#xff1a;2、3、5、7、11、13、17、19。 质数prime number又称素数有无限个。质数定义为在大于1的自然数中除了1和它本身以外不再有其他因数这样的数称为质数。例 子2、3、5、7、11、13、17、19。那时候还有一种说法叫做“质数”但是就语言上来说我觉得“素数”这种叫法和“合数”比较搭配类比于“化学元素”和“化合物”来看叫“素数”非常贴切 素数一些性质 质数p的约数只有两个1和p任一大于1的自然数要么本身是质数要么可以分解为几个质数之积这种分解是唯一的一个偶数可以写成两个合数之和其中每一个合数都最多只有9个质因数一个偶数必定可以写成一个质数加上一个合成数其中合数的因子个数有上界素数应用 数学上来看质数有很多尚未证明的特性应用上的话公钥密码是一比较好的例子了。素数对于数论就好像元素对于化学。摘自知乎 判断素数 1 //判断是否是一个素数2 int IsPrime(int x)3 {4 if(x1) //0,1负数都是非素数 5 return 0;6 int ans(int)sqrt(x)1; /*计算枚举上界为防止ans值带来的精度损失所以采用根号值取整后再加1即宁愿多枚举一个也不愿少枚举一个数 */7 for(int i2; ians; i)8 {9 if(x%i0)
10 {
11 return 0;
12 }
13 }
14 return 1;
15 } View Code 素数筛法 1.开一个大的bool型数组prime[]大小就是n1就可以了.先把所有的下标为奇数的标为true,下标为偶数的标为false. 2.代码如下 for( i3; isqrt(n); i2 )
{ if(prime[i]) for( jii; jn; ji )prime[j]false;} 3.最后输出bool数组中的值为true的单元的下标就是所求的n以内的素数了。 原理很简单就是当i是质(素)数的时候i的所有的倍数必然是合数。如果i已经被判断不是质数了那么再找到i后面的质数来把这个质数的倍数筛掉。 一个简单的筛素数的过程n30。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 第 1 步过后4 ... 28 30这15个单元被标成false,其余为true。 第 2 步开始 i3; 由于prime[3]true, 把prime[6], [9], [12], [15], [18], [21], [24], [27], [30]标为false. i4; 由于prime[4]false,不在继续筛法步骤。 i5; 由于prime[5]true, 把prime[10],[15],[20],[25],[30]标为false. i6sqrt(30)算法结束。 第 3 步把prime[]值为true的下标输出来 for(i2; i30; i) if(prime[i]) printf(%d ,i); 结果是 2 3 5 7 11 13 17 19 23 29 下图为n120的素数筛 // 1这是最原始的素数筛法
#define Max 1000000
bool prime[Max];
void IsPrime(){prime[0]prime[1]0;prime[2]1;for(int i3;imax;i)prime[i]i%20?0:1;int t(int)sqrt(Max*1.0);for(int i3;it;i)if(prime[i])for(int ji;jMax;ji)prime[j]0;
}
//2优化后的筛法手动地模拟原始筛法就可以发现某个数字可能被不止一次地删去
// 优化后的筛法就可以避免这种不必要的删去操作
#define Max 1000000
bool prime[Max];
void IsPrime(){prime[0]prime[1]0;prime[2]1;for(int i3;imax;i)prime[i]i%20?0:1;int t(int)sqrt(Max*1.0);for(int i3;it;i)if(prime[i])for(int ji*i;jMax;j2*i)//优化 prime[j]0;
} View Code 快速线性筛法 上面的方法比较好理解初始时假设全部都是素数当找到一个素数时显然这个素数乘上另外一个数之后都是合数 把这些合数都筛掉即算法名字的由来。但仔细分析能发现这种方法会造成重复筛除合数影响效率。 比如10在i2的时候k2*15筛了一次在i5k5*6 的时候又筛了一次。所以也就有了快速线性筛法。 利用了每个合数必有一个最小素因子。每个合数仅被它的最小素因子筛去正好一次。所以为线性时间。 void get_prime()
{int cnt 0;for (int i 2; i N; i){if (!tag[i]) p[cnt] i;for (int j 0; j cnt p[j] * i N; j){tag[i*p[j]] 1;if (i % p[j] 0)break;}}
} 函数模板 1 我推荐这个算法 易于理解只算奇数部分时空效率都还不错2 halfSIZE/2; 3 int sn (int) sqrt(SIZE); 4 for (i 0; i half; i) 5 p[i] true;// 初始化全部奇数为素数。p[0]对应3即p[i]对应2*i3 6 for (i 0; i sn; i) { 7 if(p[i])//如果 ii3 是素数8 { 9 for(kii3, jk*iki; j half; jk)
10 // 筛法起点是 p[i]所对应素数的平方 k^2
11 // k^2在 p 中的位置是 k*iki
12 // 下标 i k*iki
13 //对应数值 kii3 k^2
14 p[j]false;
15 }
16 }
17 //素数都存放在 p 数组中p[i]true代表 ii2 是素数。
18 //举例3是素数按3*3,3*5,3*7...的次序筛选因为只保存奇数所以不用删3*43*6.... 推荐 转载于:https://www.cnblogs.com/slp0622/p/8998445.html
