Количество простых чисел до M приблизительно равно .

Значит мой алгоритм приблизительно сделает операций.

Только что проверил, мой алгоритм на числах M >= 5504 делает в среднем больше операций, чем обычный bruteforce за .

Видимо функция в первом случае растет быстрее, чем во втором.

Когда находишь простое число p, рассматривай числа p, 2p, 3p, ... и к их счётчику количества простых делителей прибавляй 1.

тут вопрос, что значит "два простых"? Если это значит число вида pq (или p^2), то

bool is_good(int n) {
   if (n == 1) return false; //1
   n /= lp[n];
   if (n == 1) return false; //n == p
   n /= lp[n];
   if (n == 1) return true; // 2 простых
   return false; // больше чем 2 простых.
}

Если подразумевается, кол-во различных простых, то при n >= 2

cnt_different[n] = cnt_dirrerent[n / lp[n]] + (lp[n] != lp[n / lp[n]] ? 1 : 0);