A Math Contest P7 - Factors - DMOJ: Modern Online Judge

A Math Contest P7 - Factors

View as PDF

Submit solution

All submissions

Best submissions

Points: 10

Time limit: 1.0s

Memory limit: 256M

Author:

Tommy_Shan

Problem type

Define $f(x)$ ~f(x)~ as the number of factors of a positive integer $x$ ~x~. Given an integer $N$ ~N~, determine $\sum_{i=1}^N f(i)$ ~\sum_{i=1}^N f(i)~.

Input Specification

The only line contains an integer, $N$ ~N~ $(1 \le N \le 10^{12})$ ~(1 \le N \le 10^{12})~.

Output Specification

Output the value of $\sum_{i=1}^N f(i)$ ~\sum_{i=1}^N f(i)~.

Sample Input

Sample Output

Explanation for Sample

$1$ ~1~ has $1$ ~1~ factor: $1$ ~1~.

$2$ ~2~ has $2$ ~2~ factors: $1$ ~1~ and $2$ ~2~.

$3$ ~3~ has $2$ ~2~ factors: $1$ ~1~ and $3$ ~3~.

$4$ ~4~ has $3$ ~3~ factors: $1$ ~1~, $2$ ~2~, and $4$ ~4~.

$5$ ~5~ has $2$ ~2~ factors: $1$ ~1~ and $5$ ~5~.

$\sum_{i=1}^N f(i) = 1+2+2+3+2 = 10$ ~\sum_{i=1}^N f(i) = 1+2+2+3+2 = 10~

Comments

-1

RVMIA commented on April 1, 2023, 1:29 a.m.

TLE with haskell :(

1

dnialh_ commented on April 1, 2023, 4:58 p.m.

Haskell lazy evaluation isn't magic, directly factoring each of the $10^{12}$ ~10^{12}~ numbers must take at least $10^{12}$ ~10^{12}~ operations and will always be too slow.