Carmichael 3 strong pseudoprimes: Difference between revisions

Content added Content deleted

Inline

@@ Line 2,780: / Line 2,780: @@
 x  3361 x  4021 = 824389441
 </pre>
+=={{header|Swift}}==
+{{trans|Rust}}
+<lang swift>import Foundation
+extension BinaryInteger {
+  @inlinable
+  public var isPrime: Bool {
+    if self == 0 || self == 1 {
+      return false
+    } else if self == 2 {
+      return true
+    }
+    let max = Self(ceil((Double(self).squareRoot())))
+    for i in stride(from: 2, through: max, by: 1) {
+      if self % i == 0 {
+        return false
+      }
+    }
+    return true
+  }
+}
+@inlinable
+public func carmichael<T: BinaryInteger & SignedNumeric>(p1: T) -> [(T, T, T)] {
+  func mod(_ n: T, _ m: T) -> T { (n % m + m) % m }
+  var res = [(T, T, T)]()
+  guard p1.isPrime else {
+    return res
+  }
+  for h3 in stride(from: 2, to: p1, by: 1) {
+    for d in stride(from: 1, to: h3 + p1, by: 1) {
+      if (h3 + p1) * (p1 - 1) % d != 0 || mod(-p1 * p1, h3) != d % h3 {
+        continue
+      }
+      let p2 = 1 + (p1 - 1) * (h3 + p1) / d
+      guard p2.isPrime else {
+        continue
+      }
+      let p3 = 1 + p1 * p2 / h3
+      guard p3.isPrime && (p2 * p3) % (p1 - 1) == 1 else {
+        continue
+      }
+      res.append((p1, p2, p3))
+    }
+  }
+  return res
+}
+let res =
+  (1..<62)
+    .lazy
+    .filter({ $0.isPrime })
+    .map(carmichael)
+    .filter({ !$0.isEmpty })
+    .flatMap({ $0 })
+for c in res {
+  print(c)
+}</lang>
+{{out}}
+<pre>(3, 11, 17)
+(5, 29, 73)
+(5, 17, 29)
+(5, 13, 17)
+(7, 19, 67)
+...
+(61, 661, 2521)
+(61, 271, 571)
+(61, 241, 421)
+(61, 3361, 4021)</pre>
 =={{header|Tcl}}==