GESP C++ Level 5 Exam Questions (Number Theory, Greedy Points) luogu-P14073 [GESP202509 Level 5] Number Selection

**GESP Learning Resource List**
Exam Questions	Practice Questions	Syllabus Analysis
Level 1 Exam Questions List	Level 1 Practice Questions List	Level 1-5 Syllabus Analysis
Level 2 Exam Questions List	Level 2 Practice Questions List	Essential Skills for GESP/CSP Programming
Level 3 Exam Questions List	Level 3 Practice Questions List
Level 4 Exam Questions List	Level 4 Practice Questions List
Level 5 Exam Questions List	Level 5 Practice Questions List

**CSP Learning Resource List**
CSP-XL
2025 Liaoning CSP-XL Re-examination Questions Analysis

GESP C++ Level 5 exam questions from September 2025, focusing on number theory and greedy points, with a difficulty rating of ⭐⭐★☆☆, relatively easy for level 5. Difficulty level on Luogu<span>General−</span>

luogu-P14073 [GESP202509 Level 5] Number Selection

Problem Requirements

Problem Description

Given a positive integer , there are integers in total. You need to select some integers from these integers such that any two different selected integers are coprime (i.e., their greatest common divisor is ). Please maximize the number of selected integers.

For example, when , you can select integers in total. It can be verified that there is no scheme to select more integers.

Input Format

One line, a positive integer , representing the given positive integer.

Output Format

One line, a positive integer, representing the maximum number of selected integers.

Input Output Example #1

Input #1

Output #1

Input Output Example #2

Input #2

Output #2

Notes/Tips

For the test points of , it is guaranteed that .

For all test points, it is guaranteed that .

Problem Analysis

This problem mainly tests the concepts of number theory and coprimality as well as the greedy strategy.

Core Idea

The problem requires selecting as many integers as possible from to such that any two integers are coprime (greatest common divisor is 1).

1.Properties of 1:

The greatest common divisor of 1 and any positive integer is . Therefore, to maximize the count, we must select 1.

2.About numbers greater than 1:

For two integers greater than and , if they are coprime, it means they cannot have common prime factors. In other words, if our selected set contains integers greater than , then each of these integers must contain at least one prime factor, and these prime factors must be distinct (otherwise, there would be a common factor).

To maximize the selected numbers, we want each number to “consume” as few prime factors as possible. Each number greater than must have at least one prime factor. The least consuming case is wheneach number itself is a prime (containing only one prime factor).

If we select a composite number (for example, ), it occupies the “positions” of two prime factors: and . If we select , we cannot select , 3、、8、 etc. Clearly, it is more advantageous to directly select the primes and (selecting and only prevents us from selecting their multiples, but we gain integers, while selecting only gives us integers).

Greedy Strategy

In summary, the optimal selection scheme is:

Select the number 1.
Select all primes (prime numbers) between and .

The final answer is:the count of primes within + 1.

Algorithm Selection

Based on the range of (), we need an efficient method to count the number of primes.

Trial Division: Check if each number is prime. Single check takes , total complexity is . This is barely acceptable for , but not optimal.
Sieve of Eratosthenes: Time complexity is , relatively efficient, suitable for this problem.
Linear Sieve (Euler Sieve): Time complexity is , highest efficiency, suitable for larger ranges of data.

For this problem, the data range is , all three methods can pass.

Example Code

Method 1: Trial Division

#include <iostream>// Check if a number is prime// Using trial division, iterate from 2 to sqrt(num)bool isPrime(int num) {    for (int i = 2; i * i <= num; i++) {        if (num % i == 0) {            return false;  // If divisible, not prime        }    }    return true;  // Not divisible, is prime}int main() {    int n;    std::cin >> n;    // Special case: if n=1, can only select 1 number (which is 1 itself)    if (n == 1) {        std::cout << "1" << std::endl;        return 0;    }    int count = 0;    // Greedy strategy: select 1 and all primes <= n    // 1 is coprime with any number. Any two different primes are coprime.    // Primes and 1 are also coprime.    // So we count the number of primes from 2 to n    for (int i = 2; i <= n; i++) {        if (isPrime(i)) {            count++;        }    }    // Finally add 1 (since 1 is also selected)    std::cout << count + 1 << std::endl;    return 0;}

Method 2: Sieve of Eratosthenes

#include <iostream>#include <vector>// nums array used to mark whether a number is composite (not prime)// 0 indicates possible prime (initial state), 1 indicates compositeint nums[100005];int main() {    int n;    std::cin >> n;    std::vector<int> primes;  // Store found primes    // Use Sieve of Eratosthenes to find all primes from 2 to n    for (int i = 2; i <= n; i++) {        // If nums[i] is 0, then i is prime        if (nums[i] == 0) {            primes.push_back(i);            // Mark multiples of i as composite            // Start from i, increment by i (i, 2i, 3i...)            // Note: Starting from i to mark, although i is prime, marking it as 1            // does not affect subsequent checks (since i has been processed)            for (int j = i; j <= n; j += i) {                nums[j] = 1;            }        }    }    // Greedy strategy: select 1 and all primes    // Output the count of primes + 1 (this 1 represents the number 1)    std::cout << primes.size() + 1 << std::endl;    return 0;}

Method 3: Linear Sieve (Euler Sieve)

#include <iostream>#include <vector>// nums array used to mark whether a number is composite// 0 indicates prime, 1 indicates compositeint nums[100005];int main() {    int n;    std::cin >> n;    std::vector<int> primes;  // Store found primes    // Use Euler Sieve (linear sieve) to find all primes from 2 to n    for (int i = 2; i <= n; i++) {        // If nums[i] is not marked, then i is prime        if (nums[i] == 0) {            primes.push_back(i);        }        // Iterate through found primes, mark i * p as composite        for (int p : primes) {            // If the product exceeds n, stop marking            if (p * i > n) {                break;            }            nums[p * i] = 1;  // Mark p * i as composite            // Key point: if i is divisible by p, it means i = k * p            // The next number to mark is i * (next prime p') = k * p * p'            // This number will be marked by p at i' = k * p' so we can break here            // Ensure each composite is only marked by its smallest prime factor, achieving linear time complexity            if (i % p == 0) {                break;            }        }    }    // Greedy strategy: select 1 and all primes    // Output the count of primes + 1 (this 1 represents the number 1)    std::cout << primes.size() + 1 << std::endl;    return 0;}

【Recommended】Mobile Version:【GESP】C++ Certification Learning Resource Summary

【Recommended】Desktop Version:: GESP/CSP Exam Materials Website:https://wiki.coderli.com/ Dictionary-style resource organization, easy and quick to browse by category.