nefu 825 函数版素数判定

先预处理,素数筛打表的复杂度为$O(n)$,然后可以 $O(1)$ 的时间复杂度回答每次询问(总共 $T$ 次询问),总时间复杂度 $O(n+T)$。

#include <bits/stdc++.h>
using namespace std;
const int N=1e7;
int n,cnt,prime[N+10];
bool vis[N+10];
void get_prime()
{
    memset(vis,1,sizeof(vis));//标记素数为1,先假设1~N全是素数,全部初始化为1,再筛去合数。
    vis[1]=0;//1不是素数
    for(int i=2;i<=N;i++)
    {
        if(vis[i])prime[++cnt]=i;//将i加入到prime数组
        for(int j=1;j<=cnt&&i*prime[j]<=N;j++)
        {
            vis[i*prime[j]]=0;//将i*pirme[j]标记为合数
            if(i%prime[j]==0)break;//i是prime[j]倍数,退出循环
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    get_prime();
    while(cin>>n)
    {
        if(vis[n])printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

洛谷 P3383 【模板】线性筛素数

#include <bits/stdc++.h>
using namespace std;
const int N=1e8;
int n,k,t,q,cnt,prime[N+10];
bool vis[N+10];
void get_prime()
{
    memset(vis,1,sizeof(vis));
    vis[1]=0;
    for(int i=2;i<=n;i++)
    {
        if(vis[i])prime[++cnt]=i;
        for(int j=1;j<=cnt&&i*prime[j]<=N;j++)
        {
            vis[i*prime[j]]=0;
            if(i%prime[j]==0)break;
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>q;
    get_prime();
    while(q--)
    {
        cin>>k;
        printf("%d\n",prime[k]);
    }
    return 0;
}

nefu 1704 知否知否,应是绿肥红瘦

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e7;
ll x,y,z,t,cnt,prime[N+10];
bool vis[N+10];
void get_prime()
{
    memset(vis,1,sizeof(vis));
    vis[1]=0;
    for(int i=2;i<=N;i++)
    {
        if(vis[i])prime[++cnt]=i;
        for(int j=1;j<=cnt&&i*prime[j]<=N;j++)
        {
            vis[i*prime[j]]=0;
            if(i%prime[j]==0)break;
        }
    }
}
bool judge(ll x)
{
    if(x<=1)return 0;
    for(ll i=1;prime[i]*prime[i]<=x;i++)
        if(x%prime[i]==0)return 0;
    return 1;
}
int main()
{
    ios::sync_with_stdio(false);
    get_prime();
    cin>>t;
    while(t--)
    {
        cin>>x>>y>>z;
        if(judge(x+y-z))printf("yes\n");
        else printf("no\n");
    }
    return 0;
}

nefu 587 半素数

#include <bits/stdc++.h>
using namespace std;
const int N=1e6;
int n,cnt,prime[N+10];
bool vis[N+10];
void get_prime()
{
    memset(vis,1,sizeof(vis));
    vis[1]=0;
    for(int i=2;i<=N;i++)
    {
        if(vis[i])prime[++cnt]=i;
        for(int j=1;j<=cnt&&i*prime[j]<=N;j++)
        {
            vis[i*prime[j]]=0;
            if(i%prime[j]==0)break;
        }
    }
}
bool judge()
{
    for(int i=1;prime[i]*prime[i]<=n;i++)
        if(n%prime[i]==0&&vis[n/prime[i]])return 1;
    return 0;
}
int main()
{
    ios::sync_with_stdio(false);
    get_prime();
    while(cin>>n)
    {
        if(judge())printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

nefu 586 纯素数

#include <bits/stdc++.h>
using namespace std;
const int N=1e6;
int n,cnt,prime[N+10];
bool vis[N+10];
void get_prime()
{
    memset(vis,1,sizeof(vis));
    vis[1]=0;
    for(int i=2;i<=N;i++)
    {
        if(vis[i])prime[++cnt]=i;
        for(int j=1;j<=cnt&&i*prime[j]<=N;j++)
        {
            vis[i*prime[j]]=0;
            if(i%prime[j]==0)break;
        }
    }
}
bool judge(int x)
{
    int a[8],len=0;
    memset(a,0,sizeof(a));
    while(x)
    {
        a[++len]=x%10;
        x=x/10;
    }
    for(int i=1;i<=len;i++)
    {
        int s=0;
        for(int j=i;j>=1;j--)
            s=s*10+a[j];
        if(!vis[s])return 0;
    }
    return 1;
}
int main()
{
    ios::sync_with_stdio(false);
    get_prime();
    while(cin>>n)
    {
        if(judge(n))printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

nefu 781 素数与数论

#include <bits/stdc++.h>
using namespace std;
const int N=1e6;
int a,b,cnt,prime[N+10],pre[N+10];//pre表示1~i(包括i)有多少个素数,也就是前缀和
bool vis[N+10];
void get_prime()
{
    memset(vis,1,sizeof(vis));
    pre[1]=0;vis[1]=0;
    for(int i=2;i<=N;i++)
    {
        if(vis[i])prime[++cnt]=i;
        for(int j=1;j<=cnt&&i*prime[j]<=N;j++)
        {
            vis[i*prime[j]]=0;
            if(i%prime[j]==0)break;
        }
        pre[i]=cnt;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    get_prime();
    while(cin>>a>>b)
        printf("%d\n",pre[b]-pre[a-1]);
    return 0;
}

nefu 585 最大素因子

#include <bits/stdc++.h>
using namespace std;
const int N=1e6;
int n,cnt,prime[N+10],pre[N+10];
bool vis[N+10];
void get_prime()
{
    memset(vis,1,sizeof(vis));
    pre[1]=0;vis[1]=0;
    for(int i=2;i<=N;i++)
    {
        if(vis[i])prime[++cnt]=i;
        for(int j=1;j<=cnt&&i*prime[j]<=N;j++)
        {
            vis[i*prime[j]]=0;
            if(i%prime[j]==0)break;
        }
        pre[i]=cnt;//pre[i]记录i是第几个素数
    }
}
int main()
{
    ios::sync_with_stdio(false);
    get_prime();
    while(cin>>n)
    {
        if(n==1){printf("0\n");continue;}
        for(int i=n;i>=2;i--)
            if(n%i==0&&vis[i]){printf("%d\n",pre[i]);break;}
    }
    return 0;
}

nefu 1321 差点是素数

这题算综合大题了,素数筛打表+二分+区间合并,具体思路详见代码。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6;
bool vis[N+10];
ll t,l1,r1,l2,r2,l,r,tot,cnt,sum,prime[N+10],ans[N+10];
void get_prime()//素数筛打表
{
    vis[1]=1;//vis为1表示为合数
    for(ll i=2;i<=N;i++)
    {
        if(!vis[i])prime[++cnt]=i;//0表示是素数
        for(ll j=1;j<=cnt&&i*prime[j]<=N;j++)
        {
            vis[i*prime[j]]=1;//标记j*prime[i]为合数
            if(i%prime[j]==0)break;
        }
    }
}
void get_ans()//打表满足条件的数,存入ans数组,并排序
{
    for(ll i=1;i<=cnt;i++)
        for(ll j=prime[i]*prime[i];j<=1e12;j*=prime[i])
            ans[++tot]=j;
    sort(ans+1,ans+tot+1);//tot=80070 ans[tot]=999966000289
}
ll get_num(ll l,ll r)//求在[l,r]区间内满足条件的个数
{
    ll a=lower_bound(ans+1,ans+tot+1,l)-ans;
    ll b=upper_bound(ans+1,ans+tot+1,r)-ans;
    //注意下限a是lower_bound,上限b是upper_bound,可以画区间的图看一下
    return b-a;
}
int main()
{
    ios::sync_with_stdio(false);
    get_prime();get_ans();
    cin>>t;
    while(t--)
    {
        cin>>l1>>r1>>l2>>r2;
        if(l2>r1||l1>r2)sum=get_num(l1,r1)+get_num(l2,r2);//区间不重叠
        else//区间重叠
        {
            l=min(l1,l2);
            r=max(r1,r2);
            sum=get_num(l,r);
        }
        printf("%lld\n",sum);
    }
    return 0;
}

nefu 1262 五十弦翻塞外声

快速求一个数的因子和:唯一分解定理。
在这里插入图片描述
化简因子和的公式,可用等比数列求和公式:
$$1+p^1+p^2+...+p^n=\frac {p^{n+1}-1}{p-1}$$

AC代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+3;
//小于1e12的最大素数 999999999989
//大于1e6的最小素数 1e6+3  注意打表素数筛的N>=1e6+3 否则会被999999999989这个数据卡掉
ll T,n,cnt,prime[N+10];
bool vis[N+10];
void get_prime()
{
    memset(vis,1,sizeof(vis));
    vis[1]=0;
    for(int i=2;i<=N;i++)
    {
        if(vis[i])prime[++cnt]=i;
        for(int j=1;j<=cnt&&i*prime[j]<=N;j++)
        {
            vis[i*prime[j]]=0;
            if(i%prime[j]==0)break;
        }
    }
}
ll f(ll x)//求x的因子和
{
    ll s=1;
    for(ll i=1;prime[i]*prime[i]<=x;i++)//找x的素因子
    {
        if(x%prime[i]==0)
        {
            ll t=1;
            while(x%prime[i]==0)
                t=t*prime[i],x=x/prime[i];
            s*=(t*prime[i]-1)/(prime[i]-1);
        }
    }
    if(x>1)s*=(1+x);//若x未被除尽到1,说明最后的x还剩下一个素数没有乘到答案里面,把它乘进去
    return s;
}
int main()
{
    ios::sync_with_stdio(false);
    get_prime();
    cin>>T;
    while(T--)
    {
        cin>>n;
        printf("%lld\n",f(n));
    }
    return 0;
}