素?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ù)的算法。主要有以下幾種算法：
暴力法：從 2 開始，一個一個數(shù)字遍歷，判斷是否為素?cái)?shù)。
篩法：埃氏篩法和歐拉篩法是其中常用的兩種算法。
埃式篩法：對于每個合數(shù)，找到其最小的質(zhì)因數(shù)并將其標(biāo)記為合數(shù)，每次標(biāo)記一個數(shù)時都會標(biāo)記一些數(shù)，這樣逐漸縮小了搜索的范圍。
Miller-Rabin算法：是一種更快的隨機(jī)算法，它可以快速判斷一個數(shù)是否為質(zhì)數(shù)。
AKS算法：是一種判定素?cái)?shù)的算法，該算法是2002年由Manindra Agrawal，Neeraj Kayal和 Nitin Saxena所提出的。
這些算法的時間復(fù)雜度和空間復(fù)雜度各不相同，根據(jù)實(shí)際應(yī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;
}
