45 lines
1 KiB
Text
45 lines
1 KiB
Text
Sub primeSieve(limit As Uinteger, primes() As Uinteger)
|
|
Dim As Uinteger i, j
|
|
Dim As Uinteger sieve(limit)
|
|
|
|
For i = 2 To limit
|
|
sieve(i) = 1
|
|
Next
|
|
|
|
For i = 2 To limit
|
|
If sieve(i) Then
|
|
Redim Preserve primes(Ubound(primes) + 1)
|
|
primes(Ubound(primes)) = i
|
|
For j = i * i To limit Step i
|
|
sieve(j) = 0
|
|
Next
|
|
End If
|
|
Next
|
|
End Sub
|
|
|
|
Function phi(x As Uinteger, a As Uinteger, primes() As Uinteger) As Uinteger
|
|
If a <= 1 Then Return Iif(a < 1, x, x - (x \ 2))
|
|
|
|
Dim As Uinteger pa = primes(a - 1)
|
|
If x <= pa Then Return 1
|
|
|
|
Return phi(x, a - 1, primes()) - phi(x \ pa, a - 1, primes())
|
|
End Function
|
|
|
|
Function pi(n As Uinteger) As Uinteger
|
|
If n < 3 Then Return Iif(n < 2, 0, 1)
|
|
|
|
Dim As Uinteger primes()
|
|
primeSieve(Int(Sqr(n)), primes())
|
|
|
|
Dim As Uinteger a = Ubound(primes) + 1
|
|
Return phi(n, a, primes()) + a - 1
|
|
End Function
|
|
|
|
Dim As Uinteger i, n = 1
|
|
For i = 0 To 9
|
|
Print "10^" & i & " " & pi(n)
|
|
n *= 10
|
|
Next
|
|
|
|
Sleep
|