微众银行 有限域 数论 素数筛

题目描述

在抽象代数中,我们学过一个关于有限域的定理:存在一个大小为q的有限域当且仅当q是某个素数p的方幂,即q=pk ,

输入描述:

第一行包含一个整数,数的范围在[1,10000]

输出描述:

输出阶数不超过

示例1

输入

1

输出

0

示例2

输入

37

输出

19

说明

当n 为 37 时,在 1-37 范围内,以下 19 个整数可以表示成某个素数的方幂:2,3,4,5,7,8,9,11,13,16,17,19,23,25,27,29,31,32,37。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn = 1e4+5;
int vis[maxn];
int ans[maxn];
void is_prime()
{
    //1是素数,0是合数,2是素数幂
    memset(vis,1,sizeof(vis));
    vis[1]=0;
    for(int i=2;i<maxn;++i)
    {
        if(!vis[i]) continue;       
        for(int j=2;j*i<maxn;++j)
        {
            if(vis[j*i]==2) continue;
            vis[j*i]=0;
        }
        for(int j=1;j<=14;++j)
        {
            int k=j,temp=1;
            while(k--)
            {
                temp*=i;
                if(temp<0)break;
            }
            if(temp<0) continue;
            if(temp<maxn) vis[temp]=2;
        }
    }
    return ;
}
void table()
{
    int cnt=0;
    for(int i=1;i<maxn;++i)
    {
        if(vis[i]) cnt++;
        ans[i]=cnt;
    }
}
int main()
{
    is_prime();
    table();
    int n;
    while(cin>>n)
    {
        printf("%d",ans[n]);
        //cout<<ans[n]<<endl;
    }
    return 0;
}
Last modification:January 12th, 2020 at 01:11 am
如果觉得我的文章对你有用,请随意赞赏