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

90 阅读 0 评论 60 点赞

我是靠谱客的博主忧伤宝贝，这篇文章主要介绍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

复制代码

Output for the Sample Input

复制代码

问题链接：AOJ0009 Prime Number

问题简述：（略）

问题分析：（略）

程序说明：

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

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

题记：（略）

参考链接：（略）

AC的C语言程序如下：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/* 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;
}