练习-平方拆分问题线性筛法-筛质数
练习-平方拆分问题（线性筛法-筛质数）
问题描述
小蓝非常热爱数学，一天老师给小蓝出了一道数学题，想锻炼锻炼小蓝的思维能力。题目是这样的：给定两个数 a 和 b，在 a 到 b（包括 a,b）之间所有数的平方当中，试问有几个数能够表示为 x×y 的形式，其中 x 和 y 是质数。你能帮助小蓝一起来解决这个问题吗？
输入格式
第一行两个正整数 a,b，含义同题目所示。
输出格式
输出共一行，输出一个整数，代表那些能够表示为题目描述的形式的平方数的数量。
样例输入
1 5
样例输出
3
说明
样例中，在 1 到 5 之间产生的平方数为：1、4、9、16 和 25。其中只有 4、9 和 25 是满足题目要求的平方数，所以答案为 3。
解题代码：
#include using namespace std; const int N = 1e5 + 10; // 定义常量 N，表示数组的最大大小 int a, b, v[N], pri[N], cnt, ans; // 全局变量定义 // 初始化函数，使用线性筛法预处理所有质数，并标记每个数的最小质因数 void init() { for(int i = 2; i < N; i++) // 从 2 开始遍历每个数 { if(v[i] == 0) // 如果 v[i] == 0，说明 i 是质数 { v[i] = i; // 标记 i 的最小质因数是它本身 pri[++cnt] = i; // 将 i 加入质数数组 pri } for(int j = 1; j <= cnt; j++) // 遍历质数数组 pri { if(pri[j] > v[i] || pri[j] * i >= N) break; // 如果 pri[j] 大于 i 的最小质因数，或者 pri[j] * i 超出范围，则停止 v[pri[j] * i] = pri[j]; // 标记合数 pri[j] * i 的最小质因数是 pri[j] } } } int main() { cin » a » b; // 输入区间 [a, b] init(); // 调用初始化函数，预处理质数 for(int i = a; i <= b; i++) // 遍历区间 [a, b] if(v[i] == i) // 如果 v[i] == i，说明 i 是质数 ans++; // 统计质数个数 cout « ans; // 输出结果 return 0; }
1 问题分析
- 目标 ：统计区间 [a,b]内有多少个数的平方可以表示为两个质数的乘积。
- 数学性质 ：
- 如果一个数的平方可以表示为两个质数的乘积，即 n2=p×q，其中 p 和 q 是质数。
- 由于 n2=p×q，且 p 和 q 是质数，那么 n 必须是两个质数的乘积的平方根。
2 关键观察
1 平方数的性质
- 平方数 n2 的质因数分解中，每个质因数的指数都是偶数。
- 如果 n2=p×q，其中 p 和 q 是质数，那么 n 必须是两个质数的乘积的平方根。
2 质数的性质
- 质数是指只能被 1 和它本身整除的数。
- 两个质数的乘积 p×q是一个合数，且它的质因数只有 p 和 q。
3 问题的转化
- 我们需要找到区间 [a,b] 内的数 n，使得 n2 可以表示为两个质数的乘积。
- 这意味着 n 必须是两个质数的乘积的平方根。
3 解决思路
基于以上观察，我们可以设计以下解决思路：
- 预处理质数 ：
- 使用线性筛法预处理所有质数。
- 遍历区间 [a,b] ：
- 对于每个数 n，检查 n2 是否可以表示为两个质数的乘积。
- 检查 n2 是否可以表示为两个质数的乘积 ：
- 遍历质数数组
pri，检查是否存在质数 p 使得 p 和 n2/p都是质数。
4 举例说明
假设输入： a = 10, b = 20
执行过程：
- 预处理质数 ：
- 使用线性筛法预处理所有质数。
- 质数数组
pri = [2, 3, 5, 7, 11, 13, 17, 19, ...]。
- 统计区间 [10,20] 内的质数 ：
- 遍历区间 [10,20]：
- i=10：v[10]=2，不是质数。
- i=11：v[11]=11，是质数，
ans++。 - i=12：v[12]=2，不是质数。
- i=13：v[13]=13，是质数，
ans++。 - i=14：v[14]=2，不是质数。
- i=15：v[15]=3，不是质数。
- i=16：v[16]=2，不是质数。
- i=17：v[17]=17，是质数，
ans++。 - i=18：v[18]=2，不是质数。
- i=19：v[19]=19，是质数，
ans++。 - i=20：v[20]=2，不是质数。
- 结果 ：
- 质数有 11,13,17,1911,13,17,19。
ans = 4。- 输出
4。