质数判断与筛法

📌 核心概念

质数（素数）：大于1且只能被1和自身整除的自然数。

💻 算法实现

📊 算法对比

算法	时间复杂度	空间复杂度	适用场景
试除法	O(√n)	O(1)	判断单个数是否为质数
埃氏筛	O(n log log n)	O(n)	批量求质数
欧拉筛	O(n)	O(n)	大范围求质数（最优）

💡 应用场景

Go 代码

// 试除法判断质数
func isPrime(n int) bool {
    if n < 2 {
        return false
    }
    if n == 2 {
        return true
    }
    if n%2 == 0 {
        return false
    }
 
    for i := 3; i*i <= n; i += 2 {
        if n%i == 0 {
            return false
        }
    }
 
    return true
}
 
// 埃氏筛
func sieveOfEratosthenes(n int) []int {
    if n < 2 {
        return []int{}
    }
 
    isPrime := make([]bool, n+1)
    for i := range isPrime {
        isPrime[i] = true
    }
    isPrime[0], isPrime[1] = false, false
 
    for i := 2; i*i <= n; i++ {
        if isPrime[i] {
            for j := i * i; j <= n; j += i {
                isPrime[j] = false
            }
        }
    }
 
    primes := []int{}
    for i := 2; i <= n; i++ {
        if isPrime[i] {
            primes = append(primes, i)
        }
    }
 
    return primes
}
 
// 质因数分解
func primeFactorization(n int) map[int]int {
    factors := make(map[int]int)
 
    for n%2 == 0 {
        factors[2]++
        n /= 2
    }
 
    for i := 3; i*i <= n; i += 2 {
        for n%i == 0 {
            factors[i]++
            n /= i
        }
    }
 
    if n > 1 {
        factors[n] = 1
    }
 
    return factors
}

🎯 经典题目

题目	LeetCode	算法
计数质数	204	埃氏筛
丑数	263	质因数分解
丑数II	264	三指针DP
快乐数	202	数论性质
4的幂	342	位运算

---

返回：数学算法