查找特定的合数(求素数+枚举)

查找特定的合数

时间限制: 1 Sec  内存限制: 128 MB

题目描述

自然数中除了能被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

O(nlogn + n);

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

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()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	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;
}
/**/