public
class
Prime
{
public
static
void
main(String[] args)
{
long
timeStart
=
System.currentTimeMillis();
int
[] prime_array
=
new
int
[
10000
];
//
用来保存10万以下的质数(共9592个)
prime_array[
0
]
=
3
;
prime_array[
1
]
=
5
;
int
i,primeId
=-
1
,m
=
2
,prime;
//
System.out.println(2);
//
质数2直接打出^_^
for
(
int
a
=
3
; a
<=
100000
; a
+=
2
)
{
if
(m
*
m
<
a)
{
//
避免使用sqrt()
m
++
;
}
for
(i
=
0
;(prime
=
prime_array[i])
<=
m;i
++
)
{
if
(a
%
prime
==
0
)
{
break
;
}
}
if
(prime
>
m)
{
prime_array[
++
primeId]
=
a;
//
10万以下的质数存起
//
System.out.print(a+" ");
}
}
System.out.println(
"
计算10万以下的质数(共
"
+
(primeId
+
2
)
+
"
个)耗时
"
+
(System.currentTimeMillis()
-
timeStart)
+
"
毫秒.
"
);
int
maxNum
=
100000000
;
for
(
int
a
=
100001
; a
<=
maxNum; a
+=
2
)
{
if
(m
*
m
<
a)
{
//
避免使用sqrt()
m
++
;
}
for
(i
=
0
;(prime
=
prime_array[i])
<=
m;i
++
)
{
if
(a
%
prime
==
0
)
{
break
;
}
}
if
(prime
>
m)
{
++
primeId;
//
System.out.print(a+" ");
}
}
System.out.println(maxNum
+
"
以下共
"
+
(primeId
+
2
)
+
"
个质数.
"
);
System.out.println(
"
耗时
"
+
(System.currentTimeMillis()
-
timeStart)
+
"
毫秒.
"
);
}
}
