牛客求素数个数
#include <iostream>using namespace std;
int main()
{
int t,n;
cin>>t;
int a,b;
for(int i=0;i<t;i++)
{
cin>>a;
b=0;
}
for(int i=0;i<t;i++)
{ //要确保是那组数据
for(int c=2;c<=a;c++)
{
int flag=0;
for(int j=2;j<i;j++)
{
if(c%j==0)
{
flag=1;
break;
}
}
if(flag==0)
{
b++;
}
}
}
for(int i=0;i<t;i++)
{
cout<<b;
}
return 0;
}
答案是4为什么求出来9啊,还有如果不用数组是不是没有跟更简便的写法 问题出在第二个循环中的内层循环条件判断中。在判断是否为素数时,应该将内层循环的条件改为 j<=sqrt(c) ,而不是 j<i 。另外,也可以将内层循环的起始值改为2,而不是1。
修正后的代码如下:
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
int t, n;
cin >> t;
int a, b;
for (int i = 0; i < t; i++)
{
cin >> a[ i];
b[ i] = 0;
}
for (int i = 0; i < t; i++)
{
for (int c = 2; c <= a[ i]; c++)
{
int flag = 0;
for (int j = 2; j <= sqrt(c); j++)
{
if (c % j == 0)
{
flag = 1;
break;
}
}
if (flag == 0)
{
b[ i]++;
}
}
}
for (int i = 0; i < t; i++)
{
cout << b[ i];
}
return 0;
}
关于不使用数组的简便写法,可以直接在计算素数的过程中进行统计,而不需要使用额外的数组来存储结果。
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
int t, n;
cin >> t;
for (int i = 0; i < t; i++)
{
cin >> n;
int count = 0;
for (int c = 2; c <= n; c++)
{
int flag = 0;
for (int j = 2; j <= sqrt(c); j++)
{
if (c % j == 0)
{
flag = 1;
break;
}
}
if (flag == 0)
{
count++;
}
}
cout << count;
}
return 0;
}
这样就可以直接在内层循环中统计素数的个数,而不需要使用额外的数组来存储结果。 你的代码存在两个问题。
首先,在第二个 for 循环中,判断素数的内层循环应该是从 2 到根号下 c,而不是 j<i。这是因为判断素数只需要检查是否能整除到根号下 c 即可。
其次,在计算素数个数 b 时,应该将这一行放在外层循环的最后,而不是内层循环。否则,每次内层循环遇到非素数时都会执行 b++,导致计数错误。
以下是修正问题后的代码:
#include <iostream>
#include <cmath>
using namespace std;
int main() {
int t, n;
cin >> t;
int a, b;
for (int i = 0; i < t; i++) {
cin >> a;
b = 0;
}
for (int i = 0; i < t; i++) {
for (int c = 2; c <= a; c++) {
int flag = 0;
for (int j = 2; j <= sqrt(c); j++) {
if (c % j == 0) {
flag = 1;
break;
}
}
if (flag == 0) {
b++;
}
}
}
for (int i = 0; i < t; i++) {
cout << b << endl;
}
return 0;
}
关于是否可以简化代码,如果你想得到素数个数而不需要存储每个测试用例的结果,可以直接输出计数 b 的值,而不使用数组 b[]。这样可以节省空间。另外,可以注意到一个优化的点是在判断素数时,只需要从 2 到根号下 a 的范围内判断即可,无需遍历到 a。
希望能解决你的问题!如果还有其他疑问,请随时提问。
球一个最佳答案谢谢啦!这对我非常重要!{:10_254:}{:10_254:}{:10_254:}
页:
[1]