Numbers with Restricted Prime Factors
National Olympiad — National round
Submission name: multiples.cpp
Problem summary
List in increasing order all integers greater than one whose prime factors belong to the first K prime numbers. Find the N-th number, counting each value once.
Input
K N.
Output
The N-th qualifying integer.
Constraints
1 ≤ K < 1000; 1 ≤ N < 50000; the answer is guaranteed below 10^18; memory limit 2 MB and stated time limit 0.1 seconds.
Worked example
An independently prepared example for this explanation.
Input
1 4
Output
16
Solution analysis
- Generate the first K primes. Keep an auxiliary sequence starting with 1. For each prime p, maintain a pointer to the smallest generated value whose product with p has not yet been output.
- A min-heap contains the K current products. Its minimum is the next value.
- Advance every heap entry equal to that minimum, suppressing duplicates. Saturate products at 10^18 to avoid overflow outside the required range.
Why it works
Every qualifying value greater than one is a smaller qualifying value multiplied by an allowed prime. The heap merges these increasing product streams; advancing every tied stream outputs each number exactly once in sorted order.
Watch out. The auxiliary 1 is not the first answer. A number such as 6 may occur in multiple prime-product streams.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Every qualifying value greater than one is a smaller qualifying value multiplied by an
// allowed prime. The heap merges these increasing product streams; advancing every tied stream outputs
// each number exactly once in sorted order.
#include<iostream>
#include<vector>
#include<queue>
#include<utility>
#include<functional>
using namespace std;
int main(){
int k,n;
cin>>k>>n;
vector<int>p;
for(int x=2;(int)p.size()<k;x++){
bool prime=true;
for(int d:p){
if(d*d>x){
break;
}
if(x%d==0){
prime=false;
break;
}
}
if(prime){
p.push_back(x);
}
}
const unsigned long long INF=1000000000000000000ULL;
vector<unsigned long long>a(n+1);
a[0]=1;
vector<int>pos(k);
using E=pair<unsigned long long,int>;
priority_queue<E,vector<E>,greater<E>>h;
for(int j=0;j<k;j++){
h.push({(unsigned)p[j],j});
}
for(int i=1;i<=n;i++){
a[i]=h.top().first;
while(h.top().first==a[i]){
int j=h.top().second;
h.pop();
++pos[j];
auto v=a[pos[j]];
h.push({v>INF/p[j]?INF:v*p[j],j});
}
}
cout<<a[n]<<'\n';
}