CSP-J 卷

某个整数很长很长，形如：1232123212321……，其规律是从 1 开始逐一升高到 3 然后逐一降低到 1，然后又逐一升高到 3，一直到很长很长。假设最高位编号为 1，要求判断从左边最高位开始的第 $N$ 位数是几？在横线处应该填入的代码是（ ）。

01int N, M;
02cout << "请输入编号：";
03cin >> N;
04M = ____________;
05if (M != 0)
06    cout << M;
07else
08    cout << 2;

$100$ 以内最大的素数是（ ）。

$319$ 和 $377$ 的最大公约数是（ ）。

下面 C++ 代码用于判断 N（大于等于 2 的正整数）是否为质数（素数）。下面对如下代码的说法，正确的是（ ）。

01cin >> N;
02for (i = 2; i < N / 2; i++)
03    if (N % i == 0) {
04        cout << N << "不是质数";
05        break;
06    }
07if (i >= N / 2)
08    cout << N << "是质数";

阅读下面的 C++ 代码，其中变量都是整型，则说法正确的是（ ）。

01cin >> a >> b;
02while (b != 0){
03    remainder = a % b;
04    a = b;
05    b = remainder;
06}
07cout << a;

闰年的定义：

• 普通闰年：公历年份是 $4$ 的倍数，且不是 $100$ 的倍数的，为闰年（如 $2004$ 年、$2020$ 年等就是闰年）。
• 世纪闰年：公历年份是整百数的，必须是 $400$ 的倍数才是闰年（如 $1900$ 年不是闰年，$2000$ 年是闰年）。

下面程序是判断是否是闰年的正确程序。

01cin >> n;
02cout << ((n % 4 == 0 && n % 100 != 0) || (n % 400 == 0) ? 1 : 0);
03return 0;

以下 C++ 代码用于实现每个整数对应的因数，如输入 $12$，则输出 1 2 3 4 6 12；如输入 $18$，则输出 1 2 3 6 9 18。横线处应填入代码是（ ）。

01int n;
02cin>>n;
03for(int i=1;i<=n;i++)
04{
05    ____________
06    {
07        cout<<i<<" ";
08    }
09}

输入 $1$ 个正整数 $N$（$N \geq 7$），想找出它所有相邻的因数对，如，输入 $12$，因数对有 $(1,2)$、$(2,3)$、$(3,4)$。下面哪段代码找不到所有的因数对？（ ）。

质数的判定和筛法的目的并不相同，质数判定旨在判断特定的正整数是否为质数，而质数筛法意在筛选出范围内的所有质数。

素数的线性筛法时间复杂度为（ ）。

唯一分解定理描述了关于正整数的什么性质？

干支纪年法是中国传统的纪年方法，由 $10$ 个天干和 $12$ 个地支组合成 $60$ 个天干地支。由公历年份可以根据以下公式和表格换算出对应的天干地支。

天干＝（公历年份）除以 $10$ 所得余数

地支＝（公历年份）除以 $12$ 所得余数

例如，今年是 $2020$ 年，$2020$ 除以 $10$ 余数为 $0$，查表为“庚”；$2020$ 除以 $12$，余数为 $4$，查表为“子”，所以今年是庚子年。

请问 $1949$ 年的天干地支是（ ）。

小杨想写一个程序来算出正整数 N 有多少个因数，经过思考他写出了一个重复没有超过 N/2 次的循环就能够算出来了。

找出自然数 $N$ 以内的所有质数，常用算法有埃氏筛法和线性筛法，其中埃氏筛法效率更高。

素数表的埃氏筛法和线性筛法的时间复杂度都是 $O(N \log \log N)$。

在求解所有不大于 $n$ 的素数时，线性筛法（欧拉筛）都应当优先于埃氏筛法使用，因为线性筛法的时间复杂度为 $O(n)$，低于埃氏筛法的 $O(n \log \log n)$。

下面的代码用于判断整数 $n$ 是否是质数，错误的说法是（ ）。

01bool is_prime(int n) {
02    if (n <= 1) return false;
03
04    int finish_number = static_cast<int>(sqrt(n)) + 1;
05    for (int i = 2; i < finish_number; ++i) {
06        if (n % i == 0)
07            return false;
08    }
09    return true;
10}

关于埃氏筛和线性筛的比较，下列说法错误的是（ ）。

埃氏筛中将内层循环从 j = i*i 开始而不是 j = 2*i 的主要原因是（ ）。

01vector<int> eratosthenes_sieve(int n) {
02    vector<bool> is_composite(n + 1, false);
03    vector<int>  primes;
04    for (int i = 2; i <= n; i++) {
05        if (is_composite[i]) continue;
06        primes.push_back(i);
07        for (long long j = (long long)i * i; j <= n; j += i)
08            is_composite[j] = true;
09    }
10    return primes;
11}

下面关于埃氏筛法的说法正确的是（ ）。

下述代码实现素数表的埃拉托斯特尼筛法，筛选出所有小于等于 n 的素数，则横线上应填的最佳代码是（ ）。

01void sieve_Eratosthenes(int n) {
02    vector<bool> is_prime(n + 1, true);
03    vector<int> primes;
04
05    for (int i = 2; i * i <= n; i++) {
06        if (is_prime[i]) {
07            primes.push_back(i);
08            ____________ {   // 在此处填入代码
09                is_prime[j] = false;
10            }
11        }
12    }
13
14    for (int i = sqrt(n) + 1; i <= n; i++) {
15        if (is_prime[i]) {
16            primes.push_back(i);
17        }
18    }
19
20    return primes;
21}

下述代码实现素数表的线性筛法，筛选出所有小于等于 n 的素数，则横线上应填的代码是（ ）。

01vector<int> sieve_linear(int n) {
02    vector<bool> is_prime(n + 1, true);
03    vector<int> primes;
04
05    for (int i = 2; i <= n / 2; i++) {
06        if (is_prime[i])
07            primes.push_back(i);
08            ____________ {   // 在此处填入代码
09                is_prime[i * primes[j]] = 0;
10                if (i % primes[j] == 0)
11                    break;
12            }
13    }
14
15    for (int i = n / 2 + 1; i <= n; i++) {
16        if (is_prime[i])
17            primes.push_back(i);
18    }
19
20    return primes;
21}

下述代码实现素数表的埃拉托色尼（埃氏）筛法，筛选出所有小于等于 $n$ 的素数。下面说法正确的是（ ）。

01vector<int> sieve_Eratosthenes(int n) {
02    vector<bool> is_prime(n + 1, true);
03    vector<int> primes;
04
05    for (int i = 2; i * i <= n; i++) {
06        if (is_prime[i]) {
07            primes.push_back(i);
08
09            for (int j = i * i; j <= n; j += i) {
10                is_prime[j] = false;
11            }
12        }
13    }
14
15    for (int i = sqrt(n) + 1; i <= n; i++) {
16        if (is_prime[i]) {
17            primes.push_back(i);
18        }
19    }
20
21    return primes;
22}

下述代码实现素数表的线性筛法，筛选出所有小于等于 $n$ 的素数。下面说法正确的是（ ）。

01vector<int> sieve_linear(int n) {
02    vector<bool> is_prime(n + 1, true);
03    vector<int> primes;
04
05    for (int i = 2; i <= n/2; i++) {
06        if (is_prime[i])
07            primes.push_back(i);
08
09            for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) {
10                is_prime[ i * primes[j] ] = 0;
11                if (i % primes[j] == 0)
12                    break;
13            }
14    }
15
16    for (int i = n/2 +1; i <= n; i++) {
17        if (is_prime[i])
18            primes.push_back(i);
19    }
20
21    return primes;
22}

下述代码实现素数表的线性筛法，筛选出所有小于等于 n 的素数，横线上应填的最佳代码是（ ）。

01vector<int> sieve_linear(int n) {
02    vector<bool> is_prime(n + 1, true);
03    vector<int> primes;
04    if (n < 2) return primes;
05    is_prime[0] = is_prime[1] = false;
06    for (int i = 2; i <= n / 2; i++) {
07        if (is_prime[i])
08            primes.push_back(i);
09        for (int j = 0; ____________ ; j++) {   // 在此处填入代码
10            is_prime[i * primes[j]] = false;
11            if (i % primes[j] == 0)
12                break;
13        }
14    }
15    for (int i = n / 2 + 1; i <= n; i++) {
16        if (is_prime[i])
17            primes.push_back(i);
18    }
19    return primes;
20}

如下为线性筛法，用于高效生成素数表，其核心思想是每个合数只被它的最小质因数筛掉一次，时间复杂度为 $O(n)$。

01vector<int> linearSieve(int n) {
02    vector<bool> is_prime(n + 1, true);
03    vector<int> primes;
04
05    for (int i = 2; i <= n; ++i) {
06        if (is_prime[i]) {
07            primes.push_back(i);
08        }
09
10        for (int j = 0; j < primes.size() && i * primes[j] <= n; ++j) {
11            is_prime[i * primes[j]] = false;
12            if (i % primes[j] == 0) {
13                break;
14            }
15        }
16    }
17    return primes;
18}

函数 sieve 实现埃拉托斯特尼筛法(埃氏筛)，横线处应填入（ ）。

01vector<bool> sieve(int n) {
02    vector<bool> is_prime(n+1, true);
03    is_prime[0] = is_prime[1] = false;
04    for(int i = 2; i <= n; i++) {
05        if(is_prime[i]) {
06            for(int j = ____________; j <= n; j += i) {
07                is_prime[j] = false;
08            }
09        }
10    }
11    return is_prime;
12}

函数 linearSieve 实现线性筛法(欧拉筛)，横线处应填入（ ）。

01vector<int> linearSieve(int n) {
02    vector<bool> is_prime(n+1, true);
03    vector<int> primes;
04    for(int i = 2; i <= n; i++) {
05        if(is_prime[i]) primes.push_back(i);
06        for(int p : primes) {
07            if(p * i > n) break;
08            is_prime[p * i] = false;
09            if(____________) break;
10        }
11    }
12    return primes;
13}

线性筛关键是“每个合数只会被最小质因子筛到一次”，因此为 $O(n)$。

下面代码实现了欧拉（线性）筛，横线处应填写（ ）。

01vector<int> euler_sieve(int n) {
02    vector<bool> is_composite(n + 1, false);
03    vector<int>  primes;
04    for (int i = 2; i <= n; i++) {
05        if (!is_composite[i])
06            primes.push_back(i);
07        for (int j = 0; ____________ && (long long)i * primes[j] <= n; j++) {
08            is_composite[i * primes[j]] = true;
09            if (i % primes[j] == 0)
10                break;
11        }
12    }
13    return primes;
14}

线性筛相比埃氏筛的核心改进在于：埃氏筛中一个合数可能被多个质数重复标记，线性筛通过"每个合数只被其最大质因子筛去"的策略，保证每个合数恰好被标记一次，从而实现 $O(n)$ 的时间复杂度。

假设函数 gcd() 函数能正确求两个正整数的最大公约数，则下面的 lcm(a, b) 函数能正确找到两个正整数 $a$ 和 $b$ 的最小公倍数。

01int lcm(int a, int b) {
02    return a / gcd(a, b) * b;
03}

线性筛法与埃氏筛法相比的优势是（ ）。

埃氏筛法和欧拉筛法都是使用筛法思想生成素数表的算法，欧拉筛法的时间复杂度更低。（ ）

下⾯关于“唯⼀分解定理”和“素数筛法”的说法中，错误的是（ ）。

下面 init_sieve 函数的时间复杂度为（ ）。

01int sieve[MAX_N];
02void init_sieve(int n) {
03    for (int i = 1; i <= n; i++)
04        sieve[i] = i;
05    for (int i = 2; i <= n; i++)
06        for (int j = i; j <= n; j += i)
07            sieve[j]--;
08}

下面程序的时间复杂度为（ ）。

01int primes[MAXP], num = 0;
02bool isPrime[MAXN] = {false};
03void sieve() {
04    for (int n = 2; n <= MAXN; n++) {
05        if (!isPrime[n])
06            primes[num++] = n;
07        for (int i = 0; i < num && n * primes[i] <= MAXN; i++) {
08            isPrime[n * primes[i]] = true;
09            if (n % primes[i] == 0)
10                break;
11        }
12    }
13}

下⾯程序的时间复杂度为（ ）。

01bool notPrime[N] = {false};
02void sieve() {
03    for (int n = 2; n * n < N; n++)
04        if (!notPrime[n])
05            for (int i = n * n; i < N; i += n)
06                notPrime[i] = true;
07}

下面的欧氏筛法程序中，两个横线处应填入的分别是 ( )

01bool isPrime[MAXN + 1] = {false};
02int primes[MAXP], num = 0;
03void sieve() {
04    for (int n = 2; n <= MAXN; n++) {
05        if (!isPrime[n]) primes[num++] = n;
06        for (int i = 0; i < num &&  (此处1); i++) { 
07            if (此处2) 
08                break;
09        }
10    }
11}

下列程序实现了线性筛法（欧拉筛），用于在 $O(n)$ 时间内求出 $1\sim n$ 之间的所有质数。为了保证每个合数只被其最小质因子筛掉，横线处应填入的语句是（ ）。

01for (int i = 2; i <= n; i++) {
02    if (!not_prime[i]) primes[++cnt] = i;
03    for (int j = 1; j <= cnt && i * primes[j] <= n; j++) {
04        not_prime[i * primes[j]] = true;
05        if (________) break; // 在此处填入选项
06    }
07}

下列线性筛的代码片段中，当枚举到质数 $p$ 且 i % p == 0 时，使用 break 停止继续枚举。这样做的目的是（ ）。

01for (int i = 2; i <= n; ++i) {
02    if (!is_composite[i])
03        primes.push_back(i);
04    for (int p : primes) {
05        if (i * p > n)
06            break;
07        is_composite[i * p] = true;
08        if (i % p == 0)
09            break;
10    }
11}