如何高效寻找素数
Info
已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~
读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
| LeetCode | Difficulty |
|---|---|
| 204. Count Primes | 🟠 |
The definition of a prime number seems simple: if a number can only be divided by 1 and itself, then it is a prime number.
Although the definition of prime numbers is not complicated, few people can write efficient algorithms related to prime numbers.
For example, LeetCode problem #204 "Count Primes" asks you to write a function like this:
// return the number of prime numbers in the interval [2, n)
int countPrimes(int n)
// for example, countPrimes(10) returns 4
// because 2, 3, 5, 7 are prime numbers// return the number of prime numbers in the interval [2, n)
int countPrimes(int n);
// for example, countPrimes(10) returns 4
// because 2, 3, 5, 7 are prime numbers# Return the number of prime numbers in the interval [2, n)
def countPrimes(n: int) -> int:
# For example, countPrimes(10) returns 4
# because 2, 3, 5, 7 are prime numbers// return the number of prime numbers in the interval [2, n)
func countPrimes(n int) int {
}
// for example, countPrimes(10) returns 4
// because 2, 3, 5, 7 are prime numbers// return the number of prime numbers in the interval [2, n)
var countPrimes = function(n) {
};
// for example, countPrimes(10) returns 4
// because 2,3,5,7 are prime numbersHow would you write this function? I think most of you would write it like this:
int countPrimes(int n) {
int count = 0;
for (int i = 2; i < n; i++)
if (isPrime(i)) count++;
return count;
}
// determine if the integer n is a prime
boolean isPrime(int n) {
for (int i = 2; i < n; i++)
if (n % i == 0)
// has other divisors
return false;
return true;
}int countPrimes(int n) {
int count = 0;
for (int i = 2; i < n; i++)
if (isPrime(i)) count++;
return count;
}
// determine if the integer n is a prime number
bool isPrime(int n) {
for (int i = 2; i < n; i++)
if (n % i == 0)
// has other divisors
return false;
return true;
}def countPrimes(n: int) -> int:
count = 0
for i in range(2, n):
if isPrime(i):
count += 1
return count
# Determine if the integer n is a prime
def isPrime(n: int) -> bool:
for i in range(2, n):
if n % i == 0:
# There are other divisors
return False
return Truefunc countPrimes(n int) int {
count := 0
for i := 2; i < n; i++ {
if isPrime(i) {
count++
}
}
return count
}
// determine if the integer n is a prime number
func isPrime(n int) bool {
for i := 2; i < n; i++ {
if n % i == 0 {
// has other divisors
return false
}
}
return true
}var countPrimes = function(n) {
var count = 0;
for (var i = 2; i < n; i++) {
if (isPrime(i)) count++;
}
return count;
};
var isPrime = function(n) {
for (var i = 2; i < n; i++) {
if (n % i === 0) {
// has other divisors
return false;
}
}
return true;
}Writing it this way results in a time complexity of O(n^2), which is a significant issue. Firstly, using the isPrime function as an auxiliary approach is not efficient; moreover, even if you use the isPrime function, this algorithm still suffers from redundant calculations.
Let's discuss how you should write an algorithm to determine if a number is a prime. You only need to slightly modify the for loop condition in the above isPrime code:
boolean isPrime(int n) {
for (int i = 2; i * i <= n; i++)
...
}In other words, i does not need to iterate up to n, but only up to sqrt(n). Why is this? Let's take an example, assume n = 12.
12 = 2 × 6
12 = 3 × 4
12 = sqrt(12) × sqrt(12)
12 = 4 × 3
12 = 6 × 2You can see that the last two products are just the reverse of the first two, with the reversal point at sqrt(n).
In other words, if no divisible factors are found in the interval [2, sqrt(n)], you can directly conclude that n is a prime number, because no divisible factors will be found in the interval [sqrt(n), n] either.
Now, the time complexity of the isPrime function is reduced to O(sqrt(N)), but we actually don't need this function for implementing the countPrimes function. The above explanation is just to help readers understand the significance of sqrt(n), as it will be used again later.
Efficient Implementation of countPrimes
The method introduced next is called the "Sieve of Eratosthenes". This method was invented by a great scholar from ancient Greece named Eratosthenes. We've seen his name in our middle school textbooks because he was the first person to correctly calculate the circumference of the Earth using shadows, and is revered as the "Father of Geography".
Getting back to the topic, the core idea of the Sieve of Eratosthenes is the opposite of the conventional approach mentioned earlier:
First, start with 2. We know that 2 is a prime number, so 2 × 2 = 4, 3 × 2 = 6, 4 × 2 = 8... cannot be prime numbers.
Then we find that 3 is also a prime number, so 3 × 2 = 6, 3 × 3 = 9, 3 × 4 = 12... also cannot be prime numbers.
This GIF from Wikipedia illustrates it well:
Seeing this, do you start to understand the logic of this elimination method? Let's look at our first version of the code:
class Solution {
public int countPrimes(int n) {
boolean[] isPrime = new boolean[n];
// initialize the array to true
Arrays.fill(isPrime, true);
for (int i = 2; i < n; i++) {
if (isPrime[i]) {
// multiples of i cannot be prime
for (int j = 2 * i; j < n; j += i) {
isPrime[j] = false;
}
}
}
int count = 0;
for (int i = 2; i < n; i++) {
if (isPrime[i]) count++;
}
return count;
}
}class Solution {
public:
int countPrimes(int n) {
vector<bool> isPrime(n, true);
for (int i = 2; i < n; i++) {
if (isPrime[i]) {
for (int j = 2 * i; j < n; j += i) {
isPrime[j] = false;
}
}
}
int count = 0;
for (int i = 2; i < n; i++) {
if (isPrime[i]) {
count++;
}
}
return count;
}
};class Solution:
def countPrimes(self, n: int) -> int:
isPrime = [True] * n
for i in range(2, n):
if isPrime[i]:
for j in range(2 * i, n, i):
isPrime[j] = False
count = 0
for i in range(2, n):
if isPrime[i]:
count += 1
return countfunc countPrimes(n int) int {
isPrime := make([]bool, n)
for i := 0; i < n; i++ {
isPrime[i] = true
}
for i := 2; i < n; i++ {
if isPrime[i] {
for j := 2 * i; j < n; j += i {
isPrime[j] = false
}
}
}
count := 0
for i := 2; i < n; i++ {
if isPrime[i] {
count++
}
}
return count
}class Solution {
public int countPrimes(int n) {
boolean[] isPrime = new boolean[n];
Arrays.fill(isPrime, true);
for (int i = 2; i * i < n; i++) {
if (isPrime[i]) {
for (int j = i * i; j < n; j += i) {
isPrime[j] = false;
}
}
}
int count = 0;
for (int i = 2; i < n; i++) {
if (isPrime[i]) count++;
}
return count;
}
}class Solution {
public:
int countPrimes(int n) {
vector<bool> isPrime(n, true);
for (int i = 2; i * i < n; i++) {
if (isPrime[i]) {
for (int j = i * i; j < n; j += i) {
isPrime[j] = false;
}
}
}
int count = 0;
for (int i = 2; i < n; i++) {
if (isPrime[i]) {
count++;
}
}
return count;
}
};class Solution:
def countPrimes(self, n: int) -> int:
isPrime = [True] * n
for i in range(2, int(n ** 0.5) + 1):
if isPrime[i]:
for j in range(i * i, n, i):
isPrime[j] = False
count = 0
for i in range(2, n):
if isPrime[i]:
count += 1
return countfunc countPrimes(n int) int {
isPrime := make([]bool, n)
for i := 0; i < n; i++ {
isPrime[i] = true
}
for i := 2; i * i < n; i++ {
if isPrime[i] {
for j := i * i; j < n; j += i {
isPrime[j] = false
}
}
}
count := 0
for i := 2; i < n; i++ {
if isPrime[i] {
count++
}
}
return count
}var countPrimes = function(n) {
let isPrime = new Array(n).fill(true);
for (let i = 2; i * i < n; i++) {
if (isPrime[i]) {
for (let j = i * i; j < n; j += i) {
isPrime[j] = false;
}
}
}
let count = 0;
for (let i = 2; i < n; i++) {
if (isPrime[i]) count++;
}
return count;
};The time complexity of this algorithm is quite tricky to calculate. Clearly, the time depends on these two nested for loops, and the number of operations should be:
n/2 + n/3 + n/5 + n/7 + ...
= n × (1/2 + 1/3 + 1/5 + 1/7...)
The terms in the parentheses are the reciprocals of prime numbers. The final result is O(N * loglogN). Interested readers can look up the proof of this time complexity.
That's all the content related to the prime number algorithm. How does it feel? Isn't it surprising how a seemingly simple problem has so many details to refine?
