求素数个数

求素数个数

时间： 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;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。