Menghitung Bilangan Prima

Tulis fungsi countPrimes yang menerima bilangan bulat n, lalu mengembalikan jumlah bilangan prima yang kurang dari n.

Catatan: Kompleksitas waktu harus lebih baik daripada O(nlogn)

1 <= n <= 1000000

Contoh:

Input - 10

Output yang diharapkan - 4

Penjelasan - Ada 4 bilangan prima yang kurang dari 10: 2, 3, 5, 7

Input - 13

Output yang diharapkan - 5

Penjelasan - Ada 5 bilangan prima yang kurang dari 13: 2, 3, 5, 7, 11 - catat bahwa 13 tidak dihitung!