解题思路

这是一道数论题目，需要计算不超过 的素数幂的个数。主要思路如下：

  1. 判断素数：

    • 对于偶数，只需要判断2
    • 对于奇数，只需要判断到其平方根
    • 只需要用奇数去除

  2. 计算素数幂：

    • 对于每个素数 ，计算其所有不超过 的幂
    • 即计算满足 的 的个数

  3. 优化：

    • 使用 sqrt 优化素数判断
    • 使用 pow 计算幂

代码

#include <iostream>
#include <cmath>
using namespace std;

// 判断是否为素数
bool isPrime(int n) {
    if(n == 2) return true;
    if(n % 2 == 0) return false;
    
    int sqrtN = (int)sqrt(n);
    for(int i = 3; i <= sqrtN; i += 2) {
        if(n % i == 0) return false;
    }
    return true;
}

int main() {
    int n;
    cin >> n;
    int count = 0;
    
    // 遍历每个数
    for(int i = 2; i <= n; ++i) {
        if(!isPrime(i)) continue;
        
        // 计算这个素数的所有幂
        for(int k = 1; pow(i, k) <= n; k++) {
            count++;
        }
    }
    
    cout << count << endl;
    return 0;
}

import java.util.*;

public class Main {
    // 判断是否为素数
    static boolean isPrime(int n) {
        if(n == 2) return true;
        if(n % 2 == 0) return false;
        
        int sqrtN = (int)Math.sqrt(n);
        for(int i = 3; i <= sqrtN; i += 2) {
            if(n % i == 0) return false;
        }
        return true;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int count = 0;
        
        // 遍历每个数
        for(int i = 2; i <= n; ++i) {
            if(!isPrime(i)) continue;
            
            // 计算这个素数的所有幂
            for(int k = 1; Math.pow(i, k) <= n; k++) {
                count++;
            }
        }
        
        System.out.println(count);
    }
}

from math import sqrt, pow

def is_prime(n):
    """判断是否为素数"""
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    
    sqrt_n = int(sqrt(n))
    for i in range(3, sqrt_n + 1, 2):
        if n % i == 0:
            return False
    return True

def main():
    n = int(input())
    count = 0
    
    # 遍历每个数
    for i in range(2, n + 1):
        if not is_prime(i):
            continue
        
        # 计算这个素数的所有幂
        k = 1
        while pow(i, k) <= n:
            count += 1
            k += 1
    
    print(count)

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：素数判定 + 幂运算
  • 时间复杂度： - 需要遍历到 ，每次判断素数需要
  • 空间复杂度： - 只需要常数级别的额外空间