数数
友情链接：数数
题目：
思路：
这道题目主要用到了埃氏筛法（Sieve of Eratosthenes）来快速求解质数的方法，思路很巧妙，并且用到了动态规划的思想。
我们首先定义两个数组mk和p，其中mk数组用于记录这个数是否为质数，或者说转换为这个数包含了几个质数。p数组用于记录所有的质数。
整体流程是这样的：
第一部分：
初始化mk数组的值为0，表示假设最开始每一个值都是质数，接着从质数 2开始进行遍历到题目说明的最大的值，对于每一个i的值，我们首先利用mk数组进行判断i是否为一个质数，如果是一个质数，那么这个质数只包含了它本身这一个质数，就令mk[i] = 1，然后将i压入数组p中去，然后执行下面的程序；如果i不是一个质数，那么这个i一定由前面的数转换而来
[
1
]
^{[1]}
[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
]
^{[1]}
[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）。
⋮
vdots
⋮
直到
i的值在给定范围内是，判断mk[i]是否等于12，这也就是判断i的值是否由12个质数组成。如果是就进行累计，否则就继续向下执行。
整体的思路是：从前向后随着程序的推进标记出每一个非质数的值，并且标记出了每一个值是由几个质数组成的，如果这个数是一个质数，表示只有它本身组成。
代码：
#include
#include
using namespace std;
void solve() {
const long long low = 2333333, upper = 23333333;
vectorint> mk(upper + 10, 0); // 标记是否是质数或者是由几个质数转换而来的。
vectorint> 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
}
}
coutansendl;
return ;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
while(t--) {
solve();
}
return 0;
}
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
