Menghitung Banyaknya Bilangan Prima dalam Suatu Rentang

Langsung to the point ke pokok masalahnya aja ya, jadi misal diberikan dua bilangan, $n$ dan $m$, dengan $m\gt n$ gimana caranya ngehitung ada berapa bilangan prima dari $n$ sampai $m$?

Ada cara yang cukup simple, apalagi kalau $n$ dan $m$ tidak terlalu besar. Pertama, misalkan kita tahu bahwa $m$ ga akan lebih besar dari sebuah bilangan, sebut saja $max$, generate aja dulu bilangan prima dari $1$ sampai $max$ pakai Sieve of Eratosthenes, jangan lupa tandai mana yg prima dan mana yg bukan di array Boolean, sebut saja isPrime.


Habis itu, masuk bagian serunya.
Kita buat sebuah array, sebut saja arr yg sizenya $max$, lalu kita lakukan prefix sum, yang hanya menjumlah dengan 1 apabila isPrime[i] true (berarti i prima). Jangan lupa declare nilai arr semuanya 0.

Implementasinya sebagai berikut :

for(int i = 2; i<= max; i++){
  if(isPrime[i]) arr[i] = 1 + arr[i-1];
  else arr[i] = arr[i-1];
}

cout<<"Banyaknya prima dari n sampai m adalah : "<<arr[m]-arr[n-1]<<"\n";  

That's it. Correct me if I wrong. Kalau ada yg mau ditanyakan silahkan lewat kolom komentar.