NEFU-寒假大一训练六（线性筛）
A,纯素数

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll n=1e6;
int num,su[n];
bool isprime[n];
void prime()
{
    num=1;
    memset(isprime,1,sizeof(isprime));
    isprime[0]=isprime[1]=0;
    for(ll j=2;j<=n;j++)
    {
        if(isprime[j])
        su[num++]=j;
        for(ll k=1;k<num&&su[k]*j<=n;k++)
        {
            isprime[su[k]*j]=0;
            if(j%su[k]==0) break;
        }
    }
}
int main()
{
      prime();
     int x,i;
     while(~scanf("%d",&x))
     {
         int a[6],f=1;
         memset(a,0,sizeof(a));
         a[0]=x;
         a[1]=x%100000;
         a[2]=x%10000;
         a[3]=x%1000;
         a[4]=x%100;
         a[5]=x%10;
         for(i=0;i<6;i++)
         {
             if(!isprime[a[i]])
             {
                 f=0;
                 printf("NO\n");
                 break;
             }
         }
         if(f==1)
         printf("YES\n");
     }
    return 0;
}

B,素数与数论

#include <bits/stdc++.h>
using namespace std;
const int n=1e6;
int su[n],cnt,pre[n];
bool b[n];
void prime()
{
    cnt=0;
    memset(b,1,sizeof(b));
    b[0]=b[1]=0;
    for(int i=2;i<=n;i++)
    {
        if(b[i])
        su[++cnt]=i;
        pre[i]=cnt;
        for(int j=1;j<=cnt&&su[j]*i<=n;j++)
        {
            b[su[j]*i]=0;
            if(i%su[j]==0) break;
        }
    }
}
int main()
{
    prime();
    int x,y;
    int num;
    while(~scanf("%d%d",&x,&y))
    {
        printf("%d\n",pre[y]-pre[x-1]);
    }
    return 0;
}

C,函数版素数判定

#include <bits/stdc++.h>

using namespace std;
int su(int x)
{
    int f=1;
    for(int i=2;i*i<=x;i++)
    {
        if(x%i==0)
        {
            f=0;
            break;
        }
    }
    return f;
}
int main()
{
    int y;
    while(~scanf("%d",&y))
    {
        int ans=su(y);
        if(ans==1)
        printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

D,最大素因子

#include <bits/stdc++.h>
using namespace std;
const int n=1e6;
int su[n+10],cnt;
bool isprime[n+10];
void prime()
{
   cnt=0;
   memset(isprime,1,sizeof(isprime));
   isprime[0]=isprime[1]=0;
   for(int i=2;i<=n;i++)
   {
       if(isprime[i])
           su[++cnt]=i;
       for(int j=1;j<=cnt&&su[j]*i<=n;j++)
       {
           isprime[su[j]*i]=0;
           if(i%su[j]==0) break;
       }
   }
}
int main()
{
    prime();
    int x;
    while(~scanf("%d",&x))
    {
        if(x==1)
        printf("0\n");
        else
        {
            for(int k=cnt;k>=1;k--)
            {
                if(x%su[k]==0)
                {
                    printf("%d\n",k);
                    break;
                }
            }
        }
    }
    return 0;
}

E,差点是素数

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll n=1e6;
ll su[n+10],num[n+10],cnt1,cnt2,ans[n+10];
bool isprime[n+10];
void prime()
{
    cnt1=0;
    memset(isprime,1,sizeof(isprime));
    isprime[0]=isprime[1]=0;
    for(ll i=2;i<=n;i++)
    {
        if(isprime[i])
        su[++cnt1]=i;
        for(ll j=1;j<=cnt1&&su[j]*i<=n;j++)
        {
            isprime[su[j]*i]=0;
            if(i%su[j]==0) break;
        }
    }
}
void f()
{
    cnt2=0;
    for(ll k=1;k<=cnt1;k++)
    {
        for(ll v=su[k]*su[k];v<=1e12;v=v*su[k])
        {
            ans[++cnt2]=v;
        }
    }
    sort(ans+1,ans+1+cnt2);
}
ll h(ll x,ll y)
{
    ll ans1=upper_bound(ans+1,ans+1+cnt2,y)-ans;
    ll ans2=lower_bound(ans+1,ans+1+cnt2,x)-ans;
    return ans1-ans2;
}
int main()
{
    prime();
    f();
    ll t,l1,l2,r1,r2;
    while(~scanf("%lld",&t))
    {
        while(t--)
        {
            scanf("%lld %lld %lld %lld",&l1,&r1,&l2,&r2);
            if(l2>r1||l1>r2)
            {
                printf("%lld\n",h(l1,r1)+h(l2,r2));
            }
            else
            {
                ll zuo=min(l1,l2);
                ll you=max(r1,r2);
                printf("%lld\n",h(zuo,you));
            }
        }
    }
    return 0;
}

F,高木同学的因子

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int main()
{
    ll x,y;
    while(~scanf("%lld %lld",&x,&y))
    {
        ll k=__gcd(x,y);
        ll num=0,i;
        for(i=1;i*i<k;i++)
        {
            if(k%i==0)
            num+=2;
        }
        if(i*i==k)
        num+=1;
        printf("%lld\n",num);
    }
    return 0;
}

G,知否知否，应是绿肥红瘦

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll su(ll x)
{
    ll f=1;
    for(ll i=2;i*i<=x;i++)
    {
        if(x%i==0)
        {
            f=0;
            break;
        }
    }
    return f;
}
int main()
{
    ll n,a,b,c;
    while(~scanf("%lld",&n))
    {
        while(n--)
        {
            scanf("%lld %lld %lld",&a,&b,&c);
            ll m=a+b-c;
        if(su(m)==1)
        printf("yes\n");
        else printf("no\n");
        }

    }
    return 0;
}