#!/usr/bin/env python3

import math

# N = 100_000_000
N = 1_000_000_000

def print_sieve(is_prime):
    count = 0
    for i, b in enumerate(is_prime[2:]):
        if b:
            # print(i + 2)
            count += 1
    print(f"total: {count}")

def sieve(is_prime):
    sqrt_N = int(math.sqrt(N))
    for i in range(2, sqrt_N + 1):
        if is_prime[i]:
            for j in range(i * 2, N, i):
                is_prime[j] = False

def main():
    is_prime = [True for _ in range(N)]
    sieve(is_prime)
    print_sieve(is_prime)

if __name__ == '__main__':
    main()