c++ 做题总结：质数及其筛法

网址：密码：hpuacm21级寒假集训——质数及其筛法 - Virtual Judgehttps://vjudge.csgrandeur.cn/contest/476396

一：质数的筛选方法

1.试除法

bool isprimes(int n)
{
if (n == 1) return false;
for (int i=2;i<=n/i;i++) {
if (n % i == 0) return false;
}
return true;
}

2.欧拉筛

void get_primes(int n)
{
for (int i=2;i<=n;i++) {
if (!st[i]) primes[cnt ++] = i;
for (int j=0;primes[j]<=n/i;j++) {
st[primes[j]*i] = 1;
if (i%primes[j] == 0) break;
}
}
} 

二：具体题目的小知识点

1.题目E：回文质数

题解：

#include<iostream>
using namespace std;
const int N = 1e7+7;
int primes[N];
bool st[N],st1[N];
int cnt = 0;
void get_primes(int n)
{
for (int i=2;i<=n;i++) {
if (!st[i]) primes[cnt ++] = i;
for (int j=0;primes[j]<=n/i;j++) {
st[primes[j]*i] = 1;
if (i%primes[j] == 0) break;
}
}
}
void init()
{
//a
for (int i=1;i<10;i++) if (!st[i]) st1[i] = 1;
st1[11] = 1;
//aba
for (int i=1;i<10;i++)
for (int j=0;j<10;j++) st1[i*100+j*10+i] = 1;
//abcba
for (int i=1;i<10;i++)
for (int j=0;j<10;j++)
for (int k=0;k<10;k++) st1[i*10000+j*1000+k*100+j*10+i] = 1;
//abcdcba
for (int i=1;i<10;i++)
for (int j=0;j<10;j++)
for (int k=0;k<10;k++)
for (int l=0;l<10;l++) st1[i*1000000+j*100000+k*10000+l*1000+k*100+j*10+i] = 1;
}
int main()
{
get_primes(N);init();
int a,b;cin>>a>>b;
for (int i=a;i<=b&&i<=10000000;i++) if (!st[i] && st1[i]) cout<<i<<endl;
return 0;
}

1.除了11以外，所有的回文质数的位数为偶数。

2.void init( ) 中的方法称为打表法：打表法就是将题⽬中需要的答案集合提前算出来，存到代码⾥，根据题⽬所需取答案，这种⽅法通常只需要 将程序挂着，在表打完后进⾏加⼯，最终取答案程序时间复杂度为O(1)，空间复杂度为O(n)(n为答案规模)； ——沃兹·基朔德 —— 摘⾃洛⾕。

3.可以用数组值作为存储数据的标记。

2.题目G：莫比乌斯函数

题解：

#include<iostream>
using namespace std;
const int N = 1e8+8;
int primes[N],mobius[N],cnt = 0;
bool st[N];
void init(int n)
{
mobius[1] = 1;
for (int i=2;i<=n;i++) {
if(!st[i]) primes[cnt++] = i,mobius[i] = -1;
for (int j=0;primes[j]<=n/i;j++) {
st[primes[j]*i] = 1;
if (i%primes[j] == 0) break;
mobius[primes[j]*i] -= mobius[i];
}
}
}
int main()
{
init(N);
int n;
while (cin>>n && n)
{
cout<<mobius[n]<<endl;
}
return 0;
}

1.莫比乌斯函数可以用欧拉筛来求。

  已知唯一分解定理：x = p1^a1 * p2^a2 * p3^a3 * ...... * pn^an

  根据题意，需考虑三种情况：、

  （1）若x为1，则u(x) = 1;

  （2）若x为可以分解为异素数的乘积，则u(x) = (-1)^k;

  （3）若x分解的素数有重，则u(x) = 0;

  这里可以用数组mobius[]来储存并标记；

3.欧拉筛与试除法的比较

欧拉筛虽然很快，但是储存空间过大，对于题目D ，H，I,用一般的试除法显然更快。

至于其中的原理，还要等到哪天我懂得更多的时候。

最后

以上就是跳跃航空为你收集整理的c++ 做题总结：质数及其筛法的全部内容，希望文章能够帮你解决c++ 做题总结：质数及其筛法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。