Truncatable primes: Difference between revisions

← Older edit Newer edit →

Content deleted Content added

Inline

@@ Line 370: / Line 370: @@
 =={{header|C sharp|C#}}==
-<lang csharp>using System;
+<lang csharp>using System;  // 4790@3.6
-using System.Diagnostics;
+using System.Collections.Generic;
+class truncartable_primes
-namespace RosettaCode
 {
+    static void Main()
-  internal class Program
-  {
-    public static bool IsPrime(int n)
     {
-      if (n<2) return false;
+        uint m = 1000000;
+        Console.Write("L " + L(m) + " R " + R(m) + "  ");
-      if (n<4) return true;
+        var sw = System.Diagnostics.Stopwatch.StartNew();
-      if (n%2==0) return false;
-      if (n<9) return true;
+        for (int i = 1000; i > 0; i--) { L(m); R(m); }
-      if (n%3==0) return false;
+        Console.Write(sw.Elapsed); Console.Read();
-      var r = (int) Math.Sqrt(n);
-      var f = 6-1;
-      while (f<=r)
-      {
-        if (n%f==0 ||n%(f+2)==0)
-          return false;
-        f += 6;
-      }
-      return true;
     }
-    private static bool IsRightTruncatable(int n)
+    static uint L(uint n)
     {
-      for (;;)
+        n -= n & 1; n--;
+        for (uint d, d0 = 10, d1 = 100; ; n -= 2)
-      {
-        n /= 10;
+        {
-        if (n==0)
+            while (n % 3 == 0 || n % 5 == 0 || n % 7 == 0) n -= 2;
-          return true;
+            if ((d = (n % 10)) == 3 || d == 7)
-        if (!IsPrime(n))
+            {
+                while (d1 < n && n % d1 > n % d0 && isP(n % d1))
-          return false;
+                { d1 *= 10; d0 *= 10; }
-      }
+                if (d1 > n && isP(n)) return n; d0 = 10; d1 = 100;
+            }
+        }
     }
-    private static bool IsLeftTruncatable(int n)
+    static uint R(uint m)
     {
+        var p = new List<uint>() { 2, 3, 5, 7 }; uint n = 20, np;
-      string c = n.ToString();
+        for (int i = 1; i < p.Count; n = 10 * p[i++])
-      if (c.Contains("0"))
-        return false;
+        {
-      for (int i = 1; i<c.Length; i++)
+            if ((np = n + 1) >= m) break; if (isP(np)) p.Add(np);
-        if (!IsPrime(Convert.ToInt32(c.Substring(i))))
+            if ((np = n + 3) >= m) break; if (isP(np)) p.Add(np);
+            if ((np = n + 7) >= m) break; if (isP(np)) p.Add(np);
-          return false;
+            if ((np = n + 9) >= m) break; if (isP(np)) p.Add(np);
-      return true;
+        }
+        return p[p.Count - 1];
     }
-    private static void Main()
+    static bool isP(uint n)
     {
+        if (n < 7) return n == 2 || n == 3 || n == 5;
-      var sb = new Stopwatch();
+        if ((n & 1) == 0 || n % 3 == 0 || n % 5 == 0) return false;
-      sb.Start();
-      int lt = 0, rt = 0;
+        for (uint r = (uint)Math.Sqrt(n), d = 7; d <= r; d += 30)
-      for (int i = 1000000; i>0; --i)
+            if (n % (d + 00) == 0 || n % (d + 04) == 0 ||
+                n % (d + 06) == 0 || n % (d + 10) == 0 ||
-      {
-        if (IsPrime(i))
+                n % (d + 12) == 0 || n % (d + 16) == 0 ||
+                n % (d + 22) == 0 || n % (d + 24) == 0) return false;
-        {
+        return true;
-          if (rt==0 && IsRightTruncatable(i))
-            rt = i;
-          else if (lt==0 && IsLeftTruncatable(i))
-            lt = i;
-          if (lt!=0 && rt!=0)
-            break;
-        }
-      }
-      sb.Stop();
-      Console.WriteLine("Largest truncable left is={0} & right={1}, calculated in {2} msec.",
-                        lt, rt, sb.ElapsedMilliseconds);
     }
-  }
 }</lang>
-<pre>Largest truncable left is=998443 & right=739399, calculated in 16 msec.</pre>
+<pre>Output:  L 998443 R 739399   24 μs</pre>
 =={{header|Clojure}}==