Competition problem — Number theory

Library / /28 of 348

Number theory Difficulty 4.6 AIME Find the answer

Find the number of positive integers less than 1000000 which are less than or equal to the sum of their proper divisors. If your answer is $X$ and the actual value is $Y$ , your score will be $\max \left(0,20-80\left|1-\frac{X}{Y}\right|\right)$ rounded to the nearest integer.

Your answer

A number or a short expression. Spacing and $ signs are ignored.

Solution

$\mathrm{N}=1000000$ $\mathrm{s}=[0] * \mathrm{~N}$ ans $=0$ for i in range(1, N): if i <= s[i]: ans $+=1$ for $j$ in range(i + i, N, i): $s[j]+=$ i print(ans)

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.