這些求質數的算法，都是小編一點一點看的大佬們的方法，自己積累的，如果有什麼描述的不對的地方還望大佬賜教，多交流才能進步，加油，沖沖衝！！！
最基礎的暴力求質數
<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>
