问题标题: 酷町堂：3870 好大的质数

Question

1

已解决

李素妍

新手天翼

怎样用埃氏筛写，给思路

Answer 1

已采纳

李瑞曦

高级天翼

1.定义一个数组，长度为10000001。

2.输入一个数:n。

3.埃氏筛(注意：a[j]++不是a[j]=1)

4.改变计数器：i从2~n，当a[i]==0时，计数器++。

5.输出计数器。

李瑞曦在2020-05-04 21:07:26追加了内容

要采纳哟！

Answer 2

董宇昊

初级启示者

这是我们的作业

这题好坑

有一个循环要用sqrt(n)

埃氏筛

循环(int i=2;i小于等于sqrt(n);i自增)
{
如果(a[i]==0){
循环(int j=i*2;j小于等于n;j加等于i){
a[j]等于1;
}
}
}

这题数组定义10000001是过不了的

要定义100000005；

望采纳。

3870：好大的质数

Accepted：100分

董宇昊的测评结果：

测试点

结果

时间

1

Accepted

988ms

偷看一下数据

2

Accepted

360ms

偷看一下数据

3

Accepted

812ms

偷看一下数据

4

Accepted

996ms

偷看一下数据

5

Accepted

952ms

偷看一下数据

6

Accepted

64ms

偷看一下数据

7

Accepted

280ms

偷看一下数据

8

Accepted

188ms

偷看一下数据

9

Accepted

428ms

偷看一下数据

10

Accepted

804ms

偷看一下数据

Answer 3

黄子扬

初级天翼

埃氏筛有什么好写的，要写就写杜教筛、min_25和洲阁筛

黄子扬在2020-05-04 21:53:24追加了内容

给你个杜教筛代码吧

注：与此题无关

#include<bits/stdc++.h>
#include<tr1/unordered_map>
#define N 6000010
using namespace std;
template<typename T>inline void read(T &x)
{
    x=0;
    static int p;p=1;
    static char c;c=getchar();
    while(!isdigit(c)){if(c=='-')p=-1;c=getchar();}
    while(isdigit(c)) {x=(x<<1)+(x<<3)+(c-48);c=getchar();}
    x*=p;
}
bool vis[N];
int mu[N],sum1[N],phi[N];
long long sum2[N];
int cnt,prim[N];
tr1::unordered_map<long long,long long>w1;
tr1::unordered_map<int,int>w;
void get(int maxn)
{
    phi[1]=mu[1]=1;
    for(int i=2;i<=maxn;i++)
    {
        if(!vis[i])
        {
            prim[++cnt]=i;
            mu[i]=-1;phi[i]=i-1;
        }
        for(int j=1;j<=cnt&&prim[j]*i<=maxn;j++)
        {
            vis[i*prim[j]]=1;
            if(i%prim[j]==0)
            {
                phi[i*prim[j]]=phi[i]*prim[j];
                break;
            }
            else mu[i*prim[j]]=-mu[i],phi[i*prim[j]]=phi[i]*(prim[j]-1);
        }
    }
    for(int i=1;i<=maxn;i++)sum1[i]=sum1[i-1]+mu[i],sum2[i]=sum2[i-1]+phi[i];
}
int djsmu(int x)
{
    if(x<=6000000)return sum1[x];
    if(w[x])return w[x];
    int ans=1;
    for(int l=2,r;l>=0&&l<=x;l=r+1)
    {
        r=x/(x/l);
        ans-=(r-l+1)*djsmu(x/l);
    }
    return w[x]=ans;
}
long long djsphi(long long x)
{
    if(x<=6000000)return sum2[x];
    if(w1[x])return w1[x];
    long long ans=x*(x+1)/2;
    for(long long l=2,r;l<=x;l=r+1)
    {
        r=x/(x/l);
        ans-=(r-l+1)*djsphi(x/l);
    }
    return w1[x]=ans;
}
int main()
{
    int t,n;
    read(t);
    get(6000000);
    while(t--)
    {
        read(n);
        printf("%lld %d\n",djsphi(n),djsmu(n));
    }
    return 0;
}

Answer 4

黄昊轩

中级守护

int n,m;
bool a[10005];
cin>>n;
for(int i=2;i<=n;i++)
{
if(a[i]==0)
{
for(int j=2*i;j<=n;j+=i)
a[j]=1;
}
}
for(int i=2;i<=n;i++)
if(a[i]==0)
cout<<i<<" ";

埃氏筛核心，但不是这道题，输出计个数，改一下就行了

黄昊轩在2020-05-04 22:47:20追加了内容

我这是埃氏筛模板

搞错了，定义改一下，改大一点，还要有sqrt（n）

问题标题: 酷町堂：3870 好大的质数

4 个回答: