# The Problem with Naive Implementations

Implement a function that calculates the sum of the first N natural numbers.

`def sum(n: int) -> int:`
`    result = 0`
`    for i in range(n+1):`
`        result += i`
`    return result`
`sum_3 = sum(3)`
`print(sum_3)`
`    for i in range(n+1):`
`    result += i`
`import time`
`ranges = (10, 1000, 10000, 100000)`
`for n in ranges:`
`    sum(n)`
```ranges = (10, 1000, 10000, 100000)
```
`for n in ranges:`
`    start = time.process_time_ns()`
`    sum(n)`
```    end = time.process_time_ns()
```
`    exec_time = end — start`
`    print(f”sum({n}) exec time: {exec_time}ns”)`
`sum(10) exec time: 4000ns`
`sum(1000) exec time: 73000ns`
`sum(10000) exec time: 681000ns`
`sum(100000) exec time: 6990000ns`

# Applying a 2000-year-old Formula

`sum(N) = n * (n+1) / 2`
`def sum_optimized(n: int) -> int:`
`    return n * (n + 1) / 2`
`sum_optimized(10) exec time: 3000ns`
`sum_optimized(1000) exec time: 2000ns`
`sum_optimized(10000) exec time: 2000ns`
`sum_optimized(100000) exec time: 2000ns`
`sum(10) exec time: 4000ns`
`sum(1000) exec time: 73000ns`
`sum(10000) exec time: 681000ns`
`sum(100000) exec time: 6990000ns`