AOJ0009 Prime Number【筛选法＋前缀和】

65 阅读 0 评论 43 点赞

我是靠谱客的博主忧伤宝贝，最近开发中收集的这篇文章主要介绍AOJ0009 Prime Number【筛选法＋前缀和】，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Prime Number

Aizu - 0009

Write a program which reads an integer n and prints the number of prime numbers which are less than or equal to n. A prime number is a natural number which has exactly two distinct natural number divisors: 1 and itself. For example, the first four prime numbers are: 2, 3, 5 and 7.

Input

Input consists of several datasets. Each dataset has an integer n (1 ≤ n ≤ 999,999) in a line.

The number of datasets is less than or equal to 30.

Output

For each dataset, prints the number of prime numbers.

Sample Input

10
3
11

Output for the Sample Input

4
2
5

问题链接：AOJ0009 Prime Number

问题简述：（略）

问题分析：（略）

程序说明：

　　筛选法是必要的，先找出素数。

　　算一个前缀和就好了，可以查表并且确保计算时间短。

题记：（略）

参考链接：（略）

AC的C语言程序如下：

/* AOJ0009 Prime Number */

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>

using namespace std;

const int N = 1e6;
const int SQRTN = ceil(sqrt((double) N));
bool isPrime[N + 1];
int prefixsum[N + 1];

// Eratosthenes筛选法
void esieve(void)
{
    memset(isPrime, true, sizeof(isPrime));

    isPrime[0] = isPrime[1] = false;
    for(int i=2; i<=SQRTN; i++) {
        if(isPrime[i]) {
            for(int j=i*i; j<=N; j+=i)  //筛选
                isPrime[j] = false;
        }
    }
}

void maketable()
{
    prefixsum[0] = 0;
    for(int i = 1; i <= N; i++)
        prefixsum[i] = isPrime[i] ? prefixsum[i - 1] + 1 : prefixsum[i - 1];
}

int main()
{
    esieve();

    maketable();

    int n;
    while(~scanf("%d", &n))
        printf("%dn", prefixsum[n]);

    return 0;
}