上虞网站建设baidu/百度客服人工电话

题目：输入一个整数n,求n以内有多少个有限域。大小为q的有限域指的是q是某个素数p的方幂(即p^k==q,k>=1)。

分析：即0~n之间的每一个数x有多个数满足：素数^k==x，x<=n,由于这里素数在变，k值也在变，那么我们可以找出n以内所有的素数，并且如果满足：素数^k<=n,那么这个数(素数^k)就是一个有限域。

//找出n以内所有的素数(最小的素数是2)
void prime(int n,  vector<int>& v)
{for (int i = 2; i <= n; i++){int j;for (j = 2; j <= sqrt(i); j++){if (i%j == 0){break;}}if (j > sqrt(i))//是素数{v.push_back(i);}}
}int count_field()
{int n;cin >> n;vector<int> v1;//n以内的素数都存在v1中prime(n, v1);int count = 0;//对每个素数的k(k>=1)次方拿出来看看是不是在n以内for (int i = 0; i < v1.size(); i++){for (int k = 2; k <= n; k++)//因为素数单独用v1.size()算了，因此这里k从2开始{if (pow(v1[i], k) < n){count++;}else{break;}}}return count+v1.size();
}