近4年CSPJ考察情况：

	题号	题型	分值
2020	第19题	完善程序	15分
2022
2023	第18题	阅读程序	14.5分

难易度：中等

2024年备考建议

试除法和质因数分解是一个必须必须要掌握的知识点。因为其算法想法简单，但是考察确很多。究其原因，数论的内容一旦考察深了，就过难，容易没有区分度，比如2021年的筛法考察，那个题目绝大多数考生都是干瞪眼，题是很好，区分度不足。而质因数分解的难度就刚好，而且还可以和其他各种算法做结合。务必会写。

朴素试除法

判断一个数x是否是质数（很多时候称为素性测试），最简单的方法是试除法。试除，就是用2,3,...,x−1这些数字尝试整除xx。只要其中有一个数能整除x，就说明x是合数，反之是质数。

// 写成函数形式的试除法，若为合数函数返回0，为质数函数返回1
bool isPrime(int x) {
    if (x < 2) return 0;
    for (int i = 2; i < x; i++) {
        if (x % i == 0) return 0;
    }
    return 1;
}

试除法(优化后)

程序的过程，就像在数轴x−1的位置建了一堵墙，i从2开始不断右移到这堵“墙”，每次都要进行 x%i的计算，若结果为0，说明i是x的因数，x是合数。

优化上面的方法，不需要试验到x-1，而只需要试验到x​。时间复杂度也随之变为O(√x)。

// 优化后的试除法
bool isPrime(long long x) {
    if (x < 2) return 0;
    // 将 i < x 优化为 i * i <= x
    for (long long i = 2; i * i <= x; i++) {
        if (x % i == 0) return 0;
    }
    return 1;
}

分解质因数

给定一个正整数，找到它的所有因数。

考虑朴素算法，因数是成对分布的，N 的所有因数可以被分成两块，即 [2,√N​] 和 [√N​+1,N)。只需要把 [2,N][2,√N​] 里的数遍历一遍，再根据除法就可以找出至少两个因数了。这个方法的时间复杂度为 O(√N​**)**。

最简单的算法即为从 [2,√N​] 进行遍历。

vector <int> breakdown(int x) {
	vector <int> res;
	for (int i = 1; i <= x; i++) {
		if (x % i == 0) {
			while (x % i == 0) x /= i;
			res.push_back(i);
		}
	}
	if (x != 1) res.push_back(x);
	return res;
}

历年真题 试除法求质数

第一题：完善程序

#include <iostream>
using namespace std;

const int N = 110000, P = 10007;
int n;
int a[N], len;
int ans;

void getDivisor() {
    len = 0;
    for (int i = 1; ① <= n; ++i)
        if (n % i == 0) {
          a[++len] = i;
          if ( ② != i) a[++len] = n / i;
        }
}

int gcd(int a, int b) {
    if (b == 0) {
    	③ ;
    }
    return gcd(b, ④ );
}

int main() {
    cin >> n;
    getDivisor();
    ans = 0;
    for (int i = 1; i <= len; ++i) {
        for (int j = i + 1; j <= len; ++j) {
        	ans = ( ⑤ ) % P;
        }
    }
    cout << ans << endl;
    return 0;
}

填空题： 1：_________ 2：_________ 3：_________ 4：_________ 5：_________

第二题：完善程序题 （质因数分解）给出正整数 nn，请输出将 nn 质因数分解的结果，结果从小到大输出。 例如：输入 n=120，程序应该输出 2 2 2 3 5，表示：120=2×2×2×3×5。输入保证 2≤n≤10^9。提示：先从小到大枚举变量 i，然后用 i 不停试除 n 来寻找所有的质因子。 试补全程序。

1 	#include <cstdio>
2 	using namespace std;
3 	int n, i;
4 
5 	int main() {
6 	  scanf("%d", &n);
7 	  for(i = ①; ② <=n; i ++){
8 		③{
9 		  printf("%d ", i);
10		  n = n / i;
11		}
12	  }
13	  if(④)
14		printf("%d ", ⑤);
15	  return 0;
16	}

1）①处应填（ ）

A. 1

B. n-1

C. 2

D. 0

2）②处应填（ ）

A. n/i

B. n/(i*i)

C. i*i

D. i*i*i

3）③处应填（ )

A. if(n%i==0)

B. if(i*i<=n)

C. while(n%i==0)

D. while(i*i<=n)

4）④处应填（ ）

A. n>1

B. n<=1

C. i<n/i

D. i+i<=n

5）⑤处应填（ )

A. 2

B. n/i

C. n

D. i

第三题：枚举因数

（枚举因数）从小到大打印正整数 n 的所有正因数。 试补全枚举程序。

01 #include <bits/stdc++.h>
02 using namespace std;
03
04 int main() {
05   int n;
06   cin >> n;
07
08   vector<int> fac;
09   fac.reserve((int)ceil(sqrt(n)));
10
11   int i;
12   for (i = 1; i * i < n; ++i) {
13     if (①) {
14       fac.push_back(i);
15     }
16   }
17
18   for (int k = 0; k < fac.size(); ++k) {
19     cout << ② << " ";
20   }
21   if (③) {
22     cout << ④ << " ";
23   }
24   for (int k = fac.size() - 1; k >= 0; --k) {
25     cout << ⑤ << " ";
26   }
27 }

1. ①处应填（ ）

   A. n % i == 0

   B. n % i == 1

   C. n % (i-1) == 0

   D. n % (i-1) == 1

2. ②处应填（ ）

   A. n / fac[k]

   B. fac[k]

   C. fac[k]-1

   D. n / (fac[k]-1)

3. ③处应填（ ）

   A. (i-1) * (i-1) == n

   B. (i-1) * i == n

   C. i * i == n

   D. i * (i-1) == n

4. ④处应填（ ）

   A. n-i

   B. n-i+1

   C. i-1

   D. i

5. ⑤处应填（ ）

   A. n / fac[k]

   B. fac[k]

   C. fac[k]-1

   D. n / (fac[k]-1)

答题须知 1.判题时不忽略大小写，如答案为B，而你输入的答案为b，则会被判错！ 2.判题时不会忽略你输入答案的前后空格，如答案为B，而你输入的答案为空格B空格，则会被判错！ 3.判断题 A代表正确、B代表错误