Простые числа: их количество (по алгоритму http://www.programmersforum.ru/member.php?u=23819)

[Sasha_Smirnov]

Option Explicit
Sub QuickSeekForPrimes()
'Программа отмечает в натуральном ряду (примерно до 10^7) все простые числа'
'и сообщает, сколько их имеется — до выбранного вами N.'

Const top As Variant = "1 000 003"
If Not IsNumeric(Val(top)) Then MsgBox "Константа top должна быть (с) числом.": Exit Sub

Dim N, i, j, qP
N = Fix(Val(InputBox("До какого N?", "До N < 10 000 000", Val(top)))) 'Ввод N.'

If N >= 1 And N < 10 ^ 7 + 1 Then
    ReDim flags(1 To N) As Boolean
    If N >= 2 Then flags(2) = True 'то есть «2 есть простое»'
Else
    MsgBox "Измените N.": Exit Sub
End If

'Далее, в "первом приближении" - берём нечётные числа.'
For i = 3 To N Step 2: flags(i) = True: Next i


For i = 3 To Fix(Sqr(N)) Step 2 'Step 2, увы, только на 1% ускоряет поиск!'
    If flags(i) Then
        j = i + i
            Do While j <= N
            flags(j) = False '«Вырубаем» каждое j-е число.'
            j = j + i
            Loop
    End If
Next i
'По сути, «просеяли» натуральный ряд через известное РЕШЕТО ЭРАТОСФЕНА.

If N >= 2 Then qP = 1 'Посчитали первое простое число: 2.'

For i = 3 To N
qP = qP + IIf(flags(i), 1, 0)
Next i

MsgBox "Среди чисел до " & N & " программа " & _
IIf(N < 2, "не ", vbNullString) & "нашла " & qP & Space(1) & _
IIf(Right(Str$(qP), 1) = 1, "простое.", "простых.")
End Sub

[Sasha_Smirnov]

Кнопку делать не обязательно: запускается и прямо из среды VBA.

Для 10 млн (на процессоре 2,7 ГГц) "скорость продвижения" около 700 тыс. натуральных чисел в секунду, и Word работает 15 секунд (а Excel — 17).

Для бóльших же чисел время вообще неудобоваримо — и я эту возможность просто отключил, ведь легче найти в Сети.
Например, при при N, равном 100 млн, на подсчёт требуется 260 секунд (Word), а то и 315 (Excel). Но результат при этом абсолютно точный: 5761455 чисел. Спасибо, Ламер_001!

[Sasha_Smirnov]

До 200 млн имеется 11 078 937 простых (что равно 136777·81).
Врямя счёта при этом всего в 2 раза больше, чем для 100 млн.
То есть скорость почти не зависит от N. Алгоритм линейный!

Конечно, есть вообще мгновенный: N/(ln(N)–1) (по Лежандру) или (с погрешностью до 11%, по теореме Чебышёва) — интегральный логарифм от N.
Но это, как говорится, вокруг да около.