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 \leq N \leq 10^{12})$ .

Output Specification

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

Sample Input

Copy

Sample Output

Copy

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

-2

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

TLE with haskell :(

2

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.