Unprimeable numbers: Difference between revisions

Content added Content deleted

Inline

@@ Line 2,470: / Line 2,470: @@
 First unprimeable that ends with 8: 208
 First unprimeable that ends with 9: 212159
+</pre>
+=={{header|Swift}}==
+{{trans|Rust}}
+<lang swift>class BitArray {
+    var array: [UInt32]
+    init(size: Int) {
+        self.array = Array(repeating: 0, count: (size + 31)/32)
+    }
+    func get(index: Int) -> Bool {
+        let bit = UInt32(1) << (index & 31)
+        return (self.array[index >> 5] & bit) != 0
+    }
+    func set(index: Int, value: Bool) {
+        let bit = UInt32(1) << (index & 31)
+        if value {
+            self.array[index >> 5] |= bit
+        } else {
+            self.array[index >> 5] &= ~bit
+        }
+    }
+}
+class PrimeSieve {
+    var composite: BitArray
+    init(size: Int) {
+        self.composite = BitArray(size: size/2)
+        var p = 3
+        while p * p <= size {
+            if !self.composite.get(index: p/2 - 1) {
+                let inc = p * 2
+                var q = p * p
+                while q <= size {
+                    self.composite.set(index: q/2 - 1, value: true)
+                    q += inc
+                }
+            }
+            p += 2
+        }
+    }
+    func isPrime(number: Int) -> Bool {
+        if number < 2 {
+            return false
+        }
+        if (number & 1) == 0 {
+            return number == 2
+        }
+        return !self.composite.get(index: number/2 - 1)
+    }
+}
+// return number of decimal digits
+func countDigits(number: Int) -> Int {
+    var digits = 0
+    var n = number
+    while n > 0 {
+        n /= 10
+        digits += 1
+    }
+    return digits
+}
+// return the number with one digit replaced
+func changeDigit(number: Int, index: Int, digit: Int) -> Int {
+    var p = 1
+    var changed = 0
+    var n = number
+    var i = index
+    while i > 0 {
+        changed += p * (n % 10)
+        p *= 10
+        n /= 10
+        i -= 1
+    }
+    changed += (10 * (n / 10) + digit) * p
+    return changed
+}
+func unprimeable(sieve: PrimeSieve, number: Int) -> Bool {
+    if sieve.isPrime(number: number) {
+        return false
+    }
+    for i in 0..<countDigits(number: number) {
+        for j in 0..<10 {
+            let n = changeDigit(number: number, index: i, digit: j)
+            if n != number && sieve.isPrime(number: n) {
+                return false
+            }
+        }
+    }
+    return true
+}
+var count = 0
+var n = 100
+var lowest = Array(repeating: 0, count: 10)
+var found = 0
+let sieve = PrimeSieve(size: 10000000)
+print("First 35 unprimeable numbers:")
+while count < 600 || found < 10 {
+    if unprimeable(sieve: sieve, number: n) {
+        if count < 35 {
+            if count > 0 {
+                print(", ", terminator: "")
+            }
+            print(n, terminator: "")
+        }
+        count += 1
+        if count == 600 {
+            print("\n600th unprimeable number: \(n)")
+        }
+        let lastDigit = n % 10
+        if lowest[lastDigit] == 0 {
+            lowest[lastDigit] = n
+            found += 1
+        }
+    }
+    n += 1
+}
+for i in 0..<10 {
+    print("Least unprimeable number ending in \(i): \(lowest[i])")
+}</lang>
+{{out}}
+<pre>
+First 35 unprimeable numbers:
+, 204, 206, 208, 320, 322, 324, 325, 326, 328, 510, 512, 514, 515, 516, 518, 530, 532, 534, 535, 536, 538, 620, 622, 624, 625, 626, 628, 840, 842, 844, 845, 846, 848, 890
+th unprimeable number: 5242
+Least unprimeable number ending in 0: 200
+Least unprimeable number ending in 1: 595631
+Least unprimeable number ending in 2: 322
+Least unprimeable number ending in 3: 1203623
+Least unprimeable number ending in 4: 204
+Least unprimeable number ending in 5: 325
+Least unprimeable number ending in 6: 206
+Least unprimeable number ending in 7: 872897
+Least unprimeable number ending in 8: 208
+Least unprimeable number ending in 9: 212159
 </pre>