题解：SP10232 AMR11E - Distinct Primes

dsj2012 · 2024-08-26 12:33:53 · 题解

思路

这道题有 T 数据如果我们直接枚举的话应该会超时间的。

为了防止这种情况我们可以先预处理一下找出每一个有三个质因子的数。
众所周知当目前数是质数时，只要是质数倍的数那么就一定包含当前的这个质因子，那么我们就可以把那个数的质数因子加1。
那么查找质因子这个任务就交给我们的埃氏筛来实现吧。
这个时候我们只要判断这个数的质因子数是否有三个如果有放入数组之中。
查找完之后我们还要排序一下因为题目要的是第 n 个那么我们就要对里面的数进行排序。
然后我们直接输出 a_n 即可。

代码

#include<bits/stdc++.h>
using namespace std;
int T,cnt; 
int a[3005];
int vis[3005];
void work(){
    for(int i = 2 ; i <= 3000 ; i ++){
        if(vis[i] != 0)continue;
        for(int j = 1 ; j <= 3000 / i ; j ++){
            int pos = i * j;
            vis[pos] ++;
            if(vis[pos] == 3){
                a[++cnt] = pos;
            }
        }
    }
}
int main(){
    work();
    cin >> T;
    sort(a + 1 , a + 1 + cnt);
    while(T --){
        int n;
        cin >> n;
        cout << a[n] << endl;
    }
    return 0;
}