微众银行 有限域 数论 素数筛
题目描述
在抽象代数中,我们学过一个关于有限域的定理:存在一个大小为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;
}