题解

题面描述

给定一个正整数 $n$，要求统计所有不超过 $n$ 的 “漂亮数” 的个数。
这里“漂亮数”的定义为：

• $x$ 为正整数；
• 存在一个质数 $p$ 满足 $x \bmod p = 0$ 且 $p \times p \ge x$。

例如，当 $n=10$ 时，美丽数为 $2,3,4,5,6,7,9,10$，共 $8$ 个。

思路

我们可以利用质数的性质来枚举“漂亮数”。分析如下：

1. 由题意，若 $x$ 为漂亮数，则存在质数 $p$ 和正整数 $k$，使得

   $$x = p \times k$$

   且有

   $$k \le p$$

   因为 $p \times p \ge x = p \times k$，可得 $p \ge k$。

2. 对于每个质数 $p$，考虑所有满足

   $$1 \le k \le \min(p, \lfloor \frac{n}{p} \rfloor)$$

   的 $k$，则 $x = p \times k$ 均为漂亮数。

3. 直接枚举所有质数 $p$（满足 $p \le n$），然后对于每个 $p$，枚举 $k$ 的取值，将所有 $x=p \times k$ 标记。注意同一个 $x$ 可能由不同的 $p$ 得到，但只需计数一次。

代码分析

• 预处理质数：使用埃氏筛法求出不超过 $n$ 的所有质数。
• 枚举漂亮数：对于每个质数 $p$，枚举 $k=1$ 到 $\min(p, \lfloor \frac{n}{p} \rfloor)$，将 $x=p \times k$ 标记为漂亮数。
• 去重计数：利用布尔数组保证每个漂亮数只计数一次。

时间复杂度主要在于对每个质数 $p$ 的循环，枚举 $k$ 的个数最多为 $p$（当 $p$ 较小时），总体复杂度足够处理 $n\le 5\times10^6$。

C++

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

// 埃氏筛法求出不超过 n 的所有质数
vector<int> getPrimes(int n) {
    vector<bool> isPrime(n + 1, true);
    vector<int> primes;
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            primes.push_back(i);
            if ((long long)i * i <= n) { // 避免乘法溢出
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
    }
    return primes;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    // 获取质数列表
    vector<int> primes = getPrimes(n);
    
    // 使用布尔数组标记漂亮数
    vector<bool> isBeautiful(n + 1, false);
    
    // 对每个质数 p 枚举合法的 k
    for (int p : primes) {
        // 如果 p > n，则后续不可能有合法的 x
        if(p > n) break;
        // k 的上界为 min(p, n / p)
        int upper = min(p, n / p);
        for (int k = 1; k <= upper; k++) {
            int x = p * k;
            if (x <= n) {
                isBeautiful[x] = true;
            }
        }
    }
    
    // 统计漂亮数个数
    int count = 0;
    for (int i = 1; i <= n; i++) {
        if(isBeautiful[i]) count++;
    }
    
    cout << count << "\n";
    
    return 0;
}

Python

# 使用埃氏筛法求出不超过 n 的所有质数
def get_primes(n):
    is_prime = [True] * (n + 1)
    primes = []
    is_prime[0] = is_prime[1] = False
    for i in range(2, n + 1):
        if is_prime[i]:
            primes.append(i)
            if i * i <= n:
                for j in range(i * i, n + 1, i):
                    is_prime[j] = False
    return primes

def main():
    import sys
    input_data = sys.stdin.read().strip()
    if not input_data:
        return
    n = int(input_data)
    
    # 获取所有质数
    primes = get_primes(n)
    
    # 使用列表标记漂亮数
    is_beautiful = [False] * (n + 1)
    
    # 对每个质数 p 枚举合法的 k
    for p in primes:
        if p > n:
            break
        # k 的上界为 min(p, n // p)
        upper = min(p, n // p)
        for k in range(1, upper + 1):
            x = p * k
            if x <= n:
                is_beautiful[x] = True
                
    # 统计漂亮数的个数
    count = sum(is_beautiful[1:])  # 从 1 开始计数
    print(count)

if __name__ == '__main__':
    main()

Java

import java.io.*;
import java.util.*;

public class Main {
    // 埃氏筛法求出不超过 n 的所有质数
    public static List<Integer> getPrimes(int n) {
        boolean[] isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, true);
        List<Integer> primes = new ArrayList<>();
        if(n >= 0) isPrime[0] = false;
        if(n >= 1) isPrime[1] = false;
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                primes.add(i);
                if ((long)i * i <= n) {
                    for (int j = i * i; j <= n; j += i) {
                        isPrime[j] = false;
                    }
                }
            }
        }
        return primes;
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        
        // 获取质数列表
        List<Integer> primes = getPrimes(n);
        
        // 使用布尔数组标记漂亮数
        boolean[] isBeautiful = new boolean[n + 1];
        
        // 对每个质数 p 枚举合法的 k
        for (int p : primes) {
            if(p > n) break;
            // k 的上界为 min(p, n / p)
            int upper = Math.min(p, n / p);
            for (int k = 1; k <= upper; k++) {
                int x = p * k;
                if(x <= n) {
                    isBeautiful[x] = true;
                }
            }
        }
        
        // 统计漂亮数个数
        int count = 0;
        for (int i = 1; i <= n; i++) {
            if(isBeautiful[i]) count++;
        }
        System.out.println(count);
    }
}

题目内容

我们定义一个漂亮数是这样的数：

1、该数为正整数

2、设该数为 $x$ ，存在一个质数 $p$ 使得 $x$ $mod$ $p= 0$ 且 $p*p >=x$

给你一个正整数 $n$ ，你能否求出有多少漂亮数小于等于 $n$ ?

输入描述

输入一行一个正整数 $n(1≤n≤5×10^6)$。

输出描述

输出一行一个正整数，代表小于等于 $n$ 的漂亮数的个数。

样例1

输入

10

输出

8