Sleeping in Class - Help with Proof

How do you find the maximum amount of factors under 1e6?

And why is this problem in Bronze?
Problem:
http://usaco.org/index.php?page=viewproblem2&cpid=1203
Solution:
http://usaco.org/current/data/sol_prob1_bronze_feb22.html

It will definitely be at most 2\cdot \sqrt{10^6}=2\cdot 10^3. If you want to compute the answer exactly thatâ€™s also not too hard:

#include <bits/stdc++.h>
using namespace std;

int main() {
vector<int> num_divisors(1e6+1);
for (int i = 1; i < size(num_divisors); ++i) {
for (int j = i; j < size(num_divisors); j += i) {
++num_divisors[j];
}
}
int ans = 0;
for (int x: num_divisors) ans = max(ans,x);
cout << ans << "\n"; // 240
}


or see A066150 - OEIS

Why not?

2 Likes

I just think the (10^6-240) + 240 x 10^5 or (10^3+1-240) + 240 x 10^5 (I think this is the minimized complexity???) is a little hard for bronze but I donâ€™t know.

May I ask if itâ€™s true that the problems are getting harder? It seems that way to me this year.

Also, I might be asking much, but since you have a strong math background, may I ask how you would compute the largest amount of factors between a given range without coding it? Like is there any trick? Thanks

Sorry, last question, why did you do 2 x 10^3, I thought it was up to 10^3

What should it be in, then? Also, does this require anything outside of the bronze concepts?

1 Like

I donâ€™t understand this at all. Could you explain what you mean more clearly?

â€śHarderâ€ť is subjective. It wonâ€™t be hard if you improve your coding and most importantly your thinking skills.

There are at most 2 \sqrt{N} factors of Nâ€¦

The upper bound is clearly 2 \sqrt{N} factors.

What I mean is that the complexity just seems a little weird to me but idk.

Btw I donâ€™t know if I did the complexity correctly, I just assumed there were 10^6 operations, in which 240 of them consisted of 1e5 operations, and sorry, ignore the second part, I got mixed up

I was not asking a question relevant to the problem, I was just curious if it is possible to use just math to find the max factors in a given range, just through pen and paper

Iâ€™m not aware of an (easy) way to get a better bound than 2\sqrt N through pen and paper.