求素数个数
时间: 1ms 内存:128M
描述:
给你一个正整数N,在[2,N]这个区间内找出有多少个素数。
输入:
先输入一个正数T,代表有T(1<=T<=10000)组数据,然后有T行正数N(1<N<=1000 000 0)
输出:
对于每一个N,输出在这[2,N]区间内,有多少个素数;
示例输入:
1
3
示例输出:
2
提示:
参考答案(内存最优[5940]):
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int a[1000000];
bool cal(int m)
{
int n = sqrt(m);
for(long long int j=2; j <= n; j++){
if(m%j==0){
return false;
}
}
return true;
}
void fun()
{
for(int i = 2; i <= 1000000; i++){
if(cal(i)){
a[i]=1;
}
a[i] += a[i-1];
}
}
int main()
{
int n;
long long int m;
scanf("%d",&n);
fun();
while(n--){
scanf("%lld",&m);
printf("%d\n",a[m]);
}
return 0;
}
参考答案(时间最优[25]):
#include <stdio.h>
#include <stdlib.h>
int n;
int main()
{
scanf("%d",&n);
int x[n+1];
int i,j,k,max=0;
for(i=1;i<=n;i++)
{
scanf("%d",&x[i]);
if(max<x[i])
{
max=x[i];
}
}
int y[max+1];
memset(y,0,sizeof(y));
for(i=2;i<=max;i++)
{
if(y[i]==0)
{
for(j=2;j<=max/i;j++)
{
y[j*i]=1;
}
}
}
int z[max+1];
z[1]=0;
for(i=2;i<=max;i++)
{
if(y[i]==0)
z[i]=z[i-1]+1;
else
z[i]=z[i-1];
}
for(i=1;i<=n;i++)
{
printf("%d\n",z[x[i]]);
}
return 0;
}
题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。