AOJ0009Prime Number Prime Number

116 阅读 0 评论 77 点赞

我是靠谱客的博主雪白缘分，这篇文章主要介绍AOJ0009Prime Number Prime Number，现在分享给大家，希望可以做个参考。

Prime Number

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, 7.

Input

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

The number of datasets ≤ 30.

Output

For each dataset, prints the number of prime numbers.

Sample Input

复制代码

Output for the Sample Input

复制代码

复制代码

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
package 素数;

import java.util.Scanner;

public class AOJ0009_Prime_Number {

	/**
	 * @param args
	 */
	static int prime[] = new int[1000000];
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		getans();
		Scanner cin = new Scanner(System.in);
		while(cin.hasNext())
		{
			int a = cin.nextInt();
			System.out.println(prime[a]);
		}
	}
	private static void getans() {
		
		 //for(int i=0; i<1000000; i++)prime[i] = i;
		 prime[1] = 0;
		 prime[2] = 1;
		 for(int i=2; i<1000000; i++)
		 {
			 if(prime[i] == -1)
			 {
				 prime[i] = prime[i-1];continue;
			 }
			 prime[i] = prime[i-1] + 1;
			 for(int j=i*2; j<1000000; j+=i)
			 {
				 prime[j] = -1;
			 }
		 }
	}

}