Хм. Мое решение не принято?

Среди чисел, меньших m, каждое второе делится на два, каждое третье - на три, каждое четвертое - на четыре и так далее.

Следовательно, количество непростых чисел, меньших m, равно:

SUM(m%2 + m%3 + m%4 + ... + m%int(sqrt(m)))

Неоптимальный метод требует двух вычислений частных сумм, оптимальный - одного. В любом случае, вичисление требует не более, чем 2*sqrt(10"6) - 2000 итераций.