题目描述
自然数中除了能被1和本身整除外，还能被其他数整除的数叫合数。每个合数都可以写成几个质数相乘的形式，这几个质数都叫做这个合数的质因数。比如8=2×2×2，2就是8的质因数。在1—N（N≤200000）按从小到大顺序排列的自然数序列中，查找第M个有X（2≤X≤6）个不同质因数的合数。例如，第3个有2个不同质因数的合数是12（12只有2、3两个不同的质因数，在12之前有2个不同质因数的合数分别为6和10）。
输入
共1行，分别为M，X。
输出
共1行，为第M个有X个不同质因数的合数。
样例输入
复制样例数据 3 2
样例输出
12
思路：
首先介绍一种筛法——欧拉筛。将范围内的素数和合数分离开。
直接上代码
int tot,prim[200005],vis[20005]; for (int i = 2; i <= 200000; i++){//从特殊的2入手 if(!vis[i]) prim[tot++] = i;//prim数列储存素数 for (int j = 0; j < tot && prim[j] * i <= 200000; j++){ vis[i * prim[j]] = 1;//将所有素数的倍数（该数是合数）标记 if(i % prim[j] == 0) break;//（因以上原因，当是素数倍数时，开始重复，此举节约了时间） } }
通过上述思路将素数和合数分离开，这样思路容易梳理，然后进入正题。
第M个有X个不同质因数的数 从最小的素数4开始寻找，如果是素数直接跳过。
#include <bits/stdc++.h>
int m, x;
int tot, vis[200005], prim[200005];
void init(){
for (int i = 2; i <= 200000; i++){
if(!vis[i]) prim[tot++] = i;
for (int j = 0; j < tot && prim[j] * i <= 200000; j++){
vis[i * prim[j]] = 1;
if(i % prim[j] == 0) break;
}
}
}
int main()
{
init();
scanf("%d %d", &m, &x);
int ans = 0;
for (int i = 4; i <= 200000; i++){
if(!vis[i]) continue;
int num = 0;
int t = sqrt((double) i);
for (int j = 2; j <= t; j++){
if(i % j == 0){
if(!vis[j]) num++;
if(!vis[i / j] && j * j != i) num++;
}
if(num > x) break;
}
if(num == x) ans++;
if(ans == m){
printf("%d\n", i);
break;
}
}
return 0;
}
原文：https://www.cnblogs.com/Suiyue-Li/p/10915226.html