Question

编写JAVA程序,计算小于一个整数的全部素数并输出.

Answer 1

此算法很快，求2，000，000以内的素数个数只要半秒，全部打印也只要5秒。
static
void
testPrime(int
MAX)
{
long
start
=
System.currentTimeMillis();
//int
MAX
=
2000000;
BitSet
count
=
new
BitSet(MAX
+
1);
for
(int
i
=
2;
i
<=Math.sqrt(MAX);
i++)
{
int
val
=
i
*
2;
while
(val
<=
MAX
)
{
if(!count.get(val)){
count.set(val);
}
val
+=
i
;
}
}
int
counter
=
0;
for(int
i=2
;i<=
MAX;i++){
if(!count.get(i)){
System.out.println(i);
counter++;
}
}
long
end
=
System.currentTimeMillis();
System.out.println("testPrime
took
"
+
(end
-
start)
+
"
ms");
System.out.println("sum:"
+
counter);