给定整数n，请问n以内有多少个素数？
限制条件n≤106
如果要对许多整数进行素性测试，用埃氏筛法比较好
埃氏筛法原理：先将2到n范围内的所有整数写下来。其中最小的数字2是素数。将表中所有2的倍数都划去。
表中剩余的最小数字是3，它不能被更小的数整除，所以是素数。再将表中所有3的倍数都划去。
依次类推，如果表中剩余的最小数字是m时，m就是素数。然后将表中的所有m的倍数都划去。像这样反复操作，就能依次枚举n以内的素数。
2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
2 | 3 | - | 5 | - | 7 | - | 9 | - | 11 | - | 13 | - | 15 | - | 17 | - | 19 | - |
2 | 3 | - | 5 | - | 7 | - | - | - | 11 | - | 13 | - | - | - | 17 | - | 19 | - |
输入
11
输出
5(2、3、5、7、11共5个素数)
输入
1000000
输出
78498
代码语言：javascript复制import java.util.Scanner;
public class test1 {
static int[] prime = new int[1000001]; // 记录每一个素数
static boolean[] is_prime = new boolean[1000001];
public static int sieve(int n) {
int p = 0;
is_prime[0] = is_prime[1] = false;
for (int i = 2; i < n; i) {
is_prime[i] = true;
}
for (int i = 2; i <= n; i) {
if (is_prime[i] == true) {
prime[p ] = i;
for (int j = i << 1; j <= n; j = i) {
is_prime[j] = false;
}
}
}
return p;
}
// p记录了素数的个数，is_prime数组记录了测试范围每个数字是不是素数，prime数组记录每个素数
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();
cin.close();
int t = sieve(n);
System.out.println(t "个素数n分别为：");
for (int i = 0; i < t; i) {
System.out.print(prime[i] " ");
if (i % 10 == 0) {
System.out.println();
}
}
}
}用javascript实现如下：
代码语言：javascript复制<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html" charset="utf-8" />
<title>素数复习</title>
<script type="text/javascript">
var prime = new Array, is_Prime = new Array;
function isPrime(n) {
var i, j, p = 0;
for (i = 2; i < n; i) {
is_Prime[i] = true;
}
for (i = 2; i < n; i) {
if (is_Prime[i] == true) {
prime[p ] = i;
for (j = i << 1; j <= n; j = i) {
is_Prime[j] = false;
}
}
}
return p;
}
</script>
</head>
<body>
<pre><script type="text/javascript">
document.writeln("1-100所有素数:");
var p = isPrime(100), i = 0;
for (i = 0; i < p; i) {
document.write(prime[i] 't');
if ((i 1) % 5 == 0) document.writeln();
}
</script></pre>
</body>
</html>运行结果：
