问题 4577 --3.有限域(field.cpp)

4577: 3.有限域(field.cpp)

题目描述

  在抽象代数中,有一个关于有限域的定理:存在一个大小为 q的有限域当且仅当q是某个素数 p的方幂,即q=p^k,k>=1,且在同构意义下,相同大小的有限域只有一个。 
你决定运用这个定理写一个程序来计算同构意义下的不同有限域个数。对于一个给定的输入 n,你需要计算有多少个不同构的有限域,他们的大小是不超过n的。 

输入

输入文件包含多组测试数据,每组测试数据包含一个正整数n。

输出

输出文件包含多行,对于每行输入,输出阶数(即大小)不超过 n的有限域的个数。 

样例输入输出

输入#1 复制
2
37
输出#1 复制
1
19

提示

【样例说明】 
不大于 2 的有限域包括:2 
不大于 37 的有限域包括:2 3 4 5 7 8 9 11 13 16 17 19 23 25 27 29 31 32 37 
【数据规模与约定】 
对于 30%的数据,1 ≤ n ≤ 100 
对于 100%的数据,1 ≤ n ≤ 40000 

序号 标题 作者 发表时间 费用 订购数 操作