Safe primes and unsafe primes: Difference between revisions
Added Swift solution
m (→{{header|AppleScript}}: Minor tidying and optimisation in prime-sieve handler.) |
(Added Swift solution) |
||
Line 2,092:
But, who cares, these days ;-)
<br>3) time is on a 2012 MacBook 2.5Ghz i5; interpreted not jitted. Compiled/jitted time is 738ms.
=={{header|Swift}}==
<lang swift>import Foundation
class PrimeSieve {
var composite: [Bool]
init(size: Int) {
composite = Array(repeating: false, count: size/2)
var p = 3
while p * p <= size {
if !composite[p/2 - 1] {
let inc = p * 2
var q = p * p
while q <= size {
composite[q/2 - 1] = true
q += inc
}
}
p += 2
}
}
func isPrime(number: Int) -> Bool {
if number < 2 {
return false
}
if (number & 1) == 0 {
return number == 2
}
return !composite[number/2 - 1]
}
}
func commatize(_ number: Int) -> String {
let n = NSNumber(value: number)
return NumberFormatter.localizedString(from: n, number: .decimal)
}
let limit1 = 1000000
let limit2 = 10000000
class PrimeInfo {
let maxPrint: Int
var count1: Int
var count2: Int
var primes: [Int]
init(maxPrint: Int) {
self.maxPrint = maxPrint
count1 = 0
count2 = 0
primes = []
}
func addPrime(prime: Int) {
count2 += 1
if prime < limit1 {
count1 += 1
}
if count2 <= maxPrint {
primes.append(prime)
}
}
func printInfo(name: String) {
print("First \(maxPrint) \(name) primes: \(primes)")
print("Number of \(name) primes below \(commatize(limit1)): \(commatize(count1))")
print("Number of \(name) primes below \(commatize(limit2)): \(commatize(count2))")
}
}
var safePrimes = PrimeInfo(maxPrint: 35)
var unsafePrimes = PrimeInfo(maxPrint: 40)
let sieve = PrimeSieve(size: limit2)
for prime in 2..<limit2 {
if sieve.isPrime(number: prime) {
if sieve.isPrime(number: (prime - 1)/2) {
safePrimes.addPrime(prime: prime)
} else {
unsafePrimes.addPrime(prime: prime)
}
}
}
safePrimes.printInfo(name: "safe")
unsafePrimes.printInfo(name: "unsafe")</lang>
{{out}}
<pre>
First 35 safe primes: [5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479, 503, 563, 587, 719, 839, 863, 887, 983, 1019, 1187, 1283, 1307, 1319, 1367, 1439, 1487, 1523, 1619]
Number of safe primes below 1,000,000: 4,324
Number of safe primes below 10,000,000: 30,657
First 40 unsafe primes: [2, 3, 13, 17, 19, 29, 31, 37, 41, 43, 53, 61, 67, 71, 73, 79, 89, 97, 101, 103, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 173, 181, 191, 193, 197, 199, 211, 223, 229, 233]
Number of unsafe primes below 1,000,000: 74,174
Number of unsafe primes below 10,000,000: 633,922
</pre>
=={{header|Visual Basic .NET}}==
| |||