Most Divisors
Autumn Tournament (2016)
Submission name: numdiv.cpp
Problem summary
Among the integers from 1 through n, find the smallest integer with the greatest number of positive divisors. Report both the integer and its divisor count.
Input
One integer n.
Output
The selected integer on the first line and its divisor count on the second.
Constraints
1 ≤ n ≤ 3,000,000.
Worked example
Official statement sample.
Input
30
Output
24 8
Solution analysis
- Use a divisor-counting sieve. The array divisorCount[x] starts at zero and will count the positive integers dividing x.
- For every possible divisor d, visit d, 2d, 3d, and so on, adding one to each count. Each visit corresponds to a genuine divisor, so no factorization is needed. Then scan candidates in increasing order and replace the best only for a strictly larger count.
- For n = 30, both 24 and 30 have eight divisors. The increasing scan keeps 24 when it later encounters the tie at 30. Its divisors are 1, 2, 3, 4, 6, 8, 12, 24.
Why it works
The inner loop increments exactly the multiples of d. Therefore divisorCount[x] receives one increment for each positive divisor of x and no others. The final scan chooses a maximum; strict replacement in increasing order keeps its smallest achiever.
Watch out. Include 1 and n. Use a strict comparison for the smallest-number tie rule. Trial division for every candidate would be much slower.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
using namespace std;
int main(){
int n;
cin>>n;
vector<int>divisorCount(n+1,0);
for(int divisor=1;divisor<=n;divisor++){
// Every multiple has this divisor exactly once.
for(int multiple=divisor;multiple<=n;multiple+=divisor){
divisorCount[multiple]++;
}
}
int best=1;
for(int value=2;value<=n;value++){
if(divisorCount[value]>divisorCount[best]){
best=value;
}
}
cout<<best<<'\n';
cout<<divisorCount[best]<<'\n';
}