Smallest Prime Divisors of Many Numbers
Autumn Tournament (2023)
Submission name: lpd.cpp
Problem summary
Read integers until end of input and output the smallest prime divisor of each. The input families include either moderately many widely spaced values or many values packed into a short interval.
Input
Integers x>1 until EOF; there is no initial test count.
Output
One smallest prime divisor per input number, in input order.
Constraints
Four families: t≤1000,x<10^6; t≤5000,x<10^9; t≤700,x<10^12; or t≤100000,x<10^15 and max(x)−min(x)<5000000.
Worked example
Original statement sample.
Input
17 17777 771177 55135 10001
Output
17 29 3 5 73
Solution analysis
- First sieve the primes up to floor(sqrt(maximum input)). Any composite input has a prime factor in this range. Correct a floating-point square-root estimate with integer comparisons so that boundary squares are not missed.
- If all inputs occupy an interval shorter than5000000, use a segmented sieve: visit primes in increasing order and mark their multiples in that interval, recording only the first prime to reach each position. Begin at max(p²,first interval multiple), so primes themselves are not marked composite.
- Otherwise the guarantees limit the number and magnitude of inputs. Trial-divide each number by the prime list until p²>x or a divisor is found. For the sample,17777 is not divisible by2,3,5,…,23, but29 divides it; a prime such as17 remains its own smallest factor.
Why it works
In ascending prime order, the first prime marking a composite is its smallest prime divisor. Every composite up to the maximum has a factor at most its square root, hence is marked. In trial division the first dividing prime is likewise minimal; if no prime up to sqrt(x) divides x, it is prime.
Watch out. Do not expect a leading t. A plain sieve up to10^15 is impossible, while trial-dividing100000 large nearby primes wastes the interval promise. Use64-bit multiples and retain input order.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<cmath>
#include<iostream>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
vector<long long>values;
long long value;
while(cin>>value){
values.push_back(value);
}
if(values.empty()){
return 0;
}
long long low=*min_element(values.begin(),values.end());
long long high=*max_element(values.begin(),values.end());
int limit=static_cast<int>(sqrt(static_cast<long double>(high)));
while(1LL*(limit+1)*(limit+1)<=high){
limit++;
}
while(1LL*limit*limit>high){
limit--;
}
vector<bool>composite(limit+1,false);
vector<int>primes;
for(int p=2;p<=limit;p++){
if(composite[p]){
continue;
}
primes.push_back(p);
if(1LL*p*p<=limit){
for(int multiple=p*p;multiple<=limit;multiple+=p){
composite[multiple]=true;
}
}
}
if(high-low<5000000){
vector<int>firstPrime(static_cast<size_t>(high-low+1),0);
for(long long p:primes){
long long start=max(p*p,((low+p-1)/p)*p);
for(long long multiple=start;multiple<=high;multiple+=p){
int&entry=firstPrime[static_cast<size_t>(multiple-low)];
// Ascending primes ensure the first mark is the smallest divisor.
if(entry==0){
entry=static_cast<int>(p);
}
}
}
for(long long x:values){
int factor=firstPrime[static_cast<size_t>(x-low)];
cout<<(factor==0?x:factor)<<'\n';
}
}
else{
for(long long x:values){
long long answer=x;
for(long long p:primes){
if(p*p>x){
break;
}
if(x%p==0){
answer=p;
break;
}
}
cout<<answer<<'\n';
}
}
}