蓝桥杯 — — 数数

数数

友情链接：数数

题目：

思路：

这道题目主要用到了埃氏筛法（Sieve of Eratosthenes）来快速求解质数的方法，思路很巧妙，并且用到了动态规划的思想。

我们首先定义两个数组mk和p，其中mk数组用于记录这个数是否为质数，或者说转换为这个数包含了几个质数。p数组用于记录所有的质数。

整体流程是这样的：

第一部分：

初始化mk数组的值为0，表示假设最开始每一个值都是质数，接着从质数 2开始进行遍历到题目说明的最大的值，对于每一个i的值，我们首先利用mk数组进行判断i是否为一个质数，如果是一个质数，那么这个质数只包含了它本身这一个质数，就令mk[i] = 1，然后将i压入数组p中去，然后执行下面的程序；如果i不是一个质数，那么这个i一定由前面的数转换而来${}^{[1]}$，此时的mk[i] != 0，就接着往下执行。

if(!mk[i]) { // 初始的时候值为0，表示是质数
    // 记录一次2的值是由一个质因数乘积而来的
    mk[i] = 1;
    p.push_back(i);
}

第二部分：

然后进行判断i的值是否在给定的范围内，如果在给定的范围内就接着判断mk[i]的值是否等于12，如果等于12，说明i的值包含了12个质数，就将答案进行+1操作。

// 如果i小于low
if(i >= low && mk[i] == 12){
    ans++;
} 

第三部分：

最后遍历到目前为止的所有质数，即遍历数组p，将数组p中的每一个值都与i进行相乘，如果得到的结果小于所给定的范围就令mk[p[k] * i] = mk[i]+ 1，这表示p[k] * i 的值是由转变为i的所有质数+1得到的，因为p[k]是一个质数，所以要在mk[i]的基础上进行+1操作。如果得到的结果大于所给定的范围，就结束遍历数组p的操作。

// 进行遍历之前累计的所有质数
for(auto v : p){
    if(v * i >= upper) break;
    mk[v * i] = mk[i] + 1;  // 在i的所有质数的基础上进行了+1，+1是因为对于v*i又多了一个质数v
}

解释一下${}^{[1]}$处为什么i的值一定由前面的数转换而来。

我们可以这样思考：一开始对于 mk数组所有的值都是0，可以假定为初始的时候所有的值都是质数，然后我们从第一个质数2开始进行遍历，对于2，它一定是一个质数 ，因此它的值mk[2] = 1，表示2是由一个质数转化而来的，并将2压入到数组p中。对于第三部分，相当于是一个查询操作，对之后最近的非质数值进行了标记，比如现在p数组中只有一个值2，我们只能取到一个值2，然后标记2 * 2 = 4的值为非质数值，但是这一步是一个非常巧妙的过程，我们使用了一个式子mk[v * i] = mk[i] + 1，表示的是对于v * i的值是由多少个质数转变而来的，mk[i]表示的是i是由多少个质数转变而来的，+1表示的是在转变为i的质数个数的基础上又多了一个质数v。对于2而言，mk[2 * 2] = mk[2] + 1，表示的是4是由两个质数转变而来的分别是2 和 2，这样既标记了4不是一个质数，又标记了4包含了几个质数。在下一次遍历到4的时候就直接判断出4不是一个质数。

为了更好的理解，我们接着执行程序：

第二次循环：i = 3，判断出3是一个质数（因为mk[3]的值是0），令mk[3] = 1，并将3压入到p数组中去，然后判断3小于给定的范围，程序往下执行，进行查询：mk[2 * 3] = mk[3] + 1 = 2，mk[3 * 3] = mk[3] + 1 = 2

第三次循环：i = 4，由于之前已经判断出mk[4] = mk[2] + 1 = 2了，所以4不是一个质数，程序往下执行，然后4小于给定的范围，程序往下执行，进行查询：mk[2 * 4] = mk[4] + 1 = 3，mk[3 * 4] = mk[4] + 1 = 3，这就又标记出了8和12不是一个质数，并且8由3个质数的来（分别是组成4的质数22，和一个新的质数2），12也由三个质数得来（分别是组成4的质数，和一个新的质数3）。

$⋮$

直到i的值在给定范围内是，判断mk[i]是否等于12，这也就是判断i的值是否由12个质数组成。如果是就进行累计，否则就继续向下执行。

整体的思路是：从前向后随着程序的推进标记出每一个非质数的值，并且标记出了每一个值是由几个质数组成的，如果这个数是一个质数，表示只有它本身组成。

代码：

#include<iostream>
#include<vector>
using namespace std;
 
void solve() {
	const long long low = 2333333, upper = 23333333;
	vector<int> mk(upper + 10, 0);  // 标记是否是质数或者是由几个质数转换而来的。
	vector<int> p;  // 用于记录所有质数
	int ans = 0;
	for(int i = 2; i <= upper; i ++) {
		if(!mk[i]) { // 值为0时，表示i是质数
			// 记录一次i的值是由一个质因数乘积而来的
			mk[i] = 1;
			p.push_back(i);
		}
		// 如果i小于low
		if(i >= low && mk[i] == 12){
			ans++;
		} 
		// 进行遍历之前累计的所有质数
		for(auto v : p){
			if(v * i >= upper) break;
			mk[v * i] = mk[i] + 1;  // 在i的所有质数的基础上进行了+1，+1是因为对于v*i又多了一个质数v
		}
	}
	cout<<ans<<endl;
	return ;
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	while(t--) {
		solve();
	}
	return 0;
}