素?cái)?shù)算法，看看電腦是怎么找素?cái)?shù)的

素?cái)?shù)算法主要應(yīng)用于計(jì)算科學(xué)，密碼學(xué)和數(shù)論等領(lǐng)域。例如，在密碼學(xué)中，素?cái)?shù)算法用于生成密鑰；在數(shù)論中，素?cái)?shù)算法用于研究質(zhì)數(shù)分布。素?cái)?shù)算法的歷史可以追溯到公元前300年左右的古希臘數(shù)學(xué)家，他們發(fā)現(xiàn)了素?cái)?shù)的重要性。隨著數(shù)學(xué)和計(jì)算機(jī)科學(xué)的發(fā)展，素?cái)?shù)算法也在不斷改進(jìn)和提高。

素?cái)?shù)算法，是指用于求出素?cái)?shù)的算法。主要有以下幾種算法：

1. 暴力法：從 2 開(kāi)始，一個(gè)一個(gè)數(shù)字遍歷，判斷是否為素?cái)?shù)。
2. 篩法：埃氏篩法和歐拉篩法是其中常用的兩種算法。
3. 埃式篩法：對(duì)于每個(gè)合數(shù)，找到其最小的質(zhì)因數(shù)并將其標(biāo)記為合數(shù)，每次標(biāo)記一個(gè)數(shù)時(shí)都會(huì)標(biāo)記一些數(shù)，這樣逐漸縮小了搜索的范圍。
4. Miller-Rabin算法：是一種更快的隨機(jī)算法，它可以快速判斷一個(gè)數(shù)是否為質(zhì)數(shù)。
5. AKS算法：是一種判定素?cái)?shù)的算法，該算法是2002年由Manindra Agrawal，Neeraj Kayal和 Nitin Saxena所提出的。

這些算法的時(shí)間復(fù)雜度和空間復(fù)雜度各不相同，根據(jù)實(shí)際應(yīng)用場(chǎng)景選擇合適的算法即可。

Sieve of Eratosthenes 篩法求素?cái)?shù)算法代碼：

public static List<Integer> sieveOfEratosthenes(int n) {
boolean[] prime = new boolean[n + 1];
Arrays.fill(prime, true);
for (int p = 2; p * p <= n; p++) {
if (prime[p] == true) {
for (int i = p * 2; i <= n; i += p) {
prime[i] = false;
}
}
}
List<Integer> primeNumbers = new ArrayList<>();
for (int i = 2; i <= n; i++) {
if (prime[i] == true) {
primeNumbers.add(i);
}
}
return primeNumbers;
}

暴力法求素?cái)?shù)算法代碼：

public static boolean isPrime(int n) {
if (n <= 1) {
return false;
}
for (int i = 2; i < n; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}