Anonymous user
Legendre prime counting function: Difference between revisions
Legendre prime counting function (view source)
Revision as of 16:06, 29 September 2021
, 2 years agoAdd swift
(Add swift) |
|||
Line 764:
0.071464489 elapsed seconds
</pre>
=={{header|Swift}}==
<lang swift>import Foundation
func eratosthenes(limit: Int) -> [Int] {
guard limit >= 3 else {
return limit < 2 ? [] : [2]
}
let ndxLimit = (limit - 3) / 2 + 1
let bufSize = ((limit - 3) / 2) / 32 + 1
let sqrtNdxLimit = (Int(Double(limit).squareRoot()) - 3) / 2 + 1
var cmpsts = Array(repeating: 0, count: bufSize)
for ndx in 0..<sqrtNdxLimit where (cmpsts[ndx >> 5] & (1 << (ndx & 31))) == 0 {
let p = ndx + ndx + 3
var cullPos = (p * p - 3) / 2
while cullPos < ndxLimit {
cmpsts[cullPos >> 5] |= 1 << (cullPos & 31)
cullPos += p
}
}
return (-1..<ndxLimit).compactMap({i -> Int? in
if i < 0 {
return 2
} else {
if cmpsts[i >> 5] & (1 << (i & 31)) == 0 {
return .some(i + i + 3)
} else {
return nil
}
}
})
}
let primes = eratosthenes(limit: 1_000_000_000)
func φ(_ x: Int, _ a: Int) -> Int {
struct Cache {
static var cache = [String: Int]()
}
guard a != 0 else {
Cache.cache["\(x),\(a)"] = x
return Cache.cache["\(x),\(a)"]!
}
guard Cache.cache["\(x),\(a)"] == nil else {
return Cache.cache["\(x),\(a)"]!
}
Cache.cache["\(x),\(a)"] = φ(x, a - 1) - φ(x / primes[a - 1], a - 1)
return Cache.cache["\(x),\(a)"]!
}
func π(n: Int) -> Int {
guard n > 2 else {
return 0
}
let a = π(n: Int(Double(n).squareRoot()))
return φ(n, a) + a - 1
}
for i in 0..<10 {
let n = 10.pow(i)
print("π(10^\(i)) = \(π(n: n))")
}</lang>
{{out}}
<pre>π(10^0) = 0
π(10^1) = 4
π(10^2) = 25
π(10^3) = 168
π(10^4) = 1229
π(10^5) = 9592
π(10^6) = 78498
π(10^7) = 664579
π(10^8) = 5761455
π(10^9) = 50847534</pre>
=={{header|Wren}}==
| |||