这些求质数的算法，都是小编一点一点看的大佬们的方法，自己积累的，如果有什么描述的不对的地方还望大佬赐教，多交流才能进步，加油，冲冲冲！！！
最基础的暴力求质数
<code>/最基础的暴力求质数（我觉得这个的话，应该就不用多说了）
public
static
int
getPrimes
(
int
n) {
List list
= new
ArrayList<>();
for
(int
i = 2
; i < n; i++) {
boolean bool
= true
;
for
(int
j = 2
; j < i; j++) {
if
(i % j == 0
) {
bool
= false
;
break
;
}
}
if
(bool
) {
list
.add(i);
}
}
return
list
.size();
}/<code>带一些优化的暴力求质数
<code>
public
static
int
getPrimes1
(
int
n) {
if
(n 3
) {
return
0
;
}
List list
= new
ArrayList<>();
list
.add(2
);
for
(int
i = 3
; i < n; i++) {
if
((i & 1
) == 0
) {
continue
;
}
boolean bool
= true
;
for
(int
j = 3
; j * j <= i; j += 2
) {
if
(i % j == 0
) {
bool
= false
;
break
;
}
}
if
(bool
) {
list
.add(i);
}
}
return
list
.size();
}/<code>通过前面求得的质数对后面的质数进行判断
<code>
public
static
int
getPrimes2
(
int
n) {
List list
= new
ArrayList<>();
for
(int
m = 2
; m < n; m++) {
boolean isPrime = true
;
int
sqrt
= (int
) Math.sqrt
(m);
for
(Integer i : list
) {
if
(m % i == 0
) {
isPrime = false
;
break
;
}
if
(i > sqrt
) {
break
;
}
}
if
(isPrime) {
list
.add(m);
}
}
return
list
.size();
}/<code>厄拉多塞筛法
<code>
public
static
int
getPrimes3
(
int
n) {
List list
= new
ArrayList<>();
boolean[] bools = new
boolean[n];
for
(int
i = 2
; i < n; i++) {
if
(!bools[i]) {
list
.add(i);
for
(int
j = i + i; j < n; j += i) {
bools[j] = true
;
}
}
}
return
list
.size();
}/<code>Bitmap对筛法的空间优化（主要是空间优化，当然也有效率优化）
<code>/*
Bitmap对筛法的空间优化（主要是空间优化，当然也有效率优化）
这个的意思就是signs是记录的第几层，每一层分为8个
也就是int为32字节，每个字节是8个bit
(i
&
31
)==(i
%
32
)
(1
(i
&
31
))这一步是为了满足位数
signs[i
/
32
]是为了看第几层
((signs[i
/
32
]
&
(1
(i
&
31
)))
==
0
证明当前这一层的这一位并没有被记录
说明当前是个质数
循环：
循环中的j就是i的倍数，既然是倍数，就说明他不是质数
signs[j
/
32
]
|=
1
(j
&
31
);
在看这里，找到j的那一层，然后看j那一层那几位bit，如果有某一位有1存在，那这一位就是1
二进制下：
101
|
10
==
111
*/
public
static
int
getPrimes4(int
n)
{
List
list
=
new
ArrayList<>();
//一个
int
变量占用
32
字节
//如果是在C#中，提供了点阵列（BitArray）数组，那个的可读性会好很多
int[]
signs
=
new
int[n
/
32
+
1
];
for
(int
i
=
2
;
i
<
n;
i++)
{
//将元素和需确定得数字经行按位或运算，如果值改变，说明不存在该数字（未登记该数字），则其为质数。
//(当某个数为
2
的
n
次方时（n为自然数），其
&
(n
-
1
)
所得值将等价于取余运算所得值)
//*如果
x
=
2
^n
，则
x
&
(n
-
1
)
==
x
%
n
//下面判断可以写成
//if
((signs[i
/
size]
&
(1
(i
%
32
)))
==
0
)
if
((signs[i
/
32
]
&
(1
(i
&
31
)))
==
0
)
{
list.add(i);
for
(int
j
=
i
+
i;
j
<
n;
j
+=
i)
{
//登记该数字
signs[j
/
32
]
|=
1
(j
&
31
);
}
}
}
//
System.out.println(list);
return
list.size();
}
/<code>
最后来看一下各个求质数方法的效果图（这里用的是一百万以内的质数）
这里附上全部代码
<code>import
java.util.ArrayList;import
java.util.List;public
class
Primes
{public
static
void
main
(String[] args)
{long
start = System.currentTimeMillis(); System.out.println(getPrimes(1000000
));long
end = System.currentTimeMillis(); System.out.println("最基础的暴力求质数"
+ (end - start) +"毫秒"
); start = System.currentTimeMillis(); System.out.println(getPrimes1(1000000
)); end = System.currentTimeMillis(); System.out.println("带一些优化的暴力求质数"
+ (end - start) +"毫秒"
); start = System.currentTimeMillis(); System.out.println(getPrimes2(1000000
)); end = System.currentTimeMillis(); System.out.println("通过前面求得的质数对后面的质数进行判断"
+ (end - start) +"毫秒"
); start = System.currentTimeMillis(); System.out.println(getPrimes3(1000000
)); end = System.currentTimeMillis(); System.out.println("厄拉多塞筛法"
+ (end - start) +"毫秒"
); start = System.currentTimeMillis(); System.out.println(getPrimes4(1000000
)); end = System.currentTimeMillis(); System.out.println("Bitmap对筛法的空间优化（主要是空间优化，当然也有效率优化）"
+ (end - start) +"毫秒"
); }public
static
int
getPrimes
(
int
n) { Listlist
=new
ArrayList<>();for
(int
i =2
; i < n; i++) { booleanbool
=true
;for
(int
j =2
; j < i; j++) {if
(i % j ==0
) {bool
=false
;break
; } }if
(bool
) {list
.add(i); } }return
list
.size(); }public
static
int
getPrimes1
(
int
n) {if
(n3
) {return
0
; } Listlist
=new
ArrayList<>();list
.add(2
);for
(int
i =3
; i < n; i++) {if
((i &1
) ==0
) {continue
; } booleanbool
=true
;for
(int
j =3
; j * j <= i; j +=2
) {if
(i % j ==0
) {bool
=false
;break
; } }if
(bool
) {list
.add(i); } }return
list
.size(); }public
static
int
getPrimes2
(
int
n) { Listlist
=new
ArrayList<>();for
(int
m =2
; m < n; m++) { boolean isPrime =true
;int
sqrt
= (int
) Math.sqrt
(m);for
(Integer i :list
) {if
(m % i ==0
) { isPrime =false
;break
; }if
(i >sqrt
) {break
; } }if
(isPrime) {list
.add(m); } }return
list
.size(); }public
static
int
getPrimes3
(
int
n) { Listlist
=new
ArrayList<>(); boolean[] bools =new
boolean[n];for
(int
i =2
; i < n; i++) {if
(!bools[i]) {list
.add(i);for
(int
j = i + i; j < n; j += i) { bools[j] =true
; } } }return
list
.size(); }public
static
int
getPrimes4
(
int
n) { Listlist
=new
ArrayList<>();int
[] signs =new
int
[n /32
+1
];for
(int
i =2
; i < n; i++) {if
((signs[i /32
] & (1
<< (i &31
))) ==0
) {list
.add(i);for
(int
j = i + i; j < n; j += i) { signs[j /32
] |=1
<< (j &31
); } } }return
list
.size(); } }/<code>
