SHARE
TWEET

Magic square of prime numbers solver

a guest Mar 23rd, 2015 492 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4.  
  5. namespace MagicPrimeSquare
  6. {
  7.     class Program
  8.     {
  9.         static void Main()
  10.         {
  11.             bool[] isPrime = new bool[480];
  12.             isPrime[2] = true;
  13.             for (int i = 2; i < 480; i++)
  14.             {
  15.                 isPrime[i] = true;
  16.             }
  17.             for (int i = 2; i < 480; i++)
  18.             {
  19.                 if (isPrime[i])
  20.                 {
  21.                     for (int j = 2 * i; j < 480; j += i)
  22.                     {
  23.                         isPrime[j] = false;
  24.                     }
  25.                 }
  26.             }
  27.  
  28.             var oddPrimesUpTo480 = new List<int>();
  29.             for (int idx = 3; idx < 480; idx++)
  30.             {
  31.                 if (isPrime[idx])
  32.                 {
  33.                     oddPrimesUpTo480.Add(idx);
  34.                 }
  35.             }
  36.  
  37.             // Magic square:
  38.             // a b c
  39.             // d e f
  40.             // g h i
  41.             //
  42.             // Sums: S1 = a + b + c, S2 = d + e + f, S3 = g + h + i, S4 = a + d + g, S5 = b + e + h, S6 = c + f + i, S7 = c + e + g, S8 = a + e + i
  43.  
  44.             var recordSum = 366;
  45.  
  46.             foreach (var a in oddPrimesUpTo480)
  47.             {
  48.                 foreach (var b in oddPrimesUpTo480)
  49.                 {
  50.                     if (b == a) continue;
  51.                     foreach (var c in oddPrimesUpTo480)
  52.                     {
  53.                         // To show progress
  54.                         // Console.WriteLine("a b c = {0} {1} {2}", a, b, c);
  55.  
  56.                         var s1 = a + b + c;
  57.                         if (!oddPrimesUpTo480.Contains(s1)) continue;
  58.                         if ((s1 == a) || (s1 == b)) continue;
  59.                         if (s1 >= recordSum) continue;
  60.  
  61.                         if ((c == s1) || (c == b) || (c == a)) continue;
  62.                         foreach (var d in oddPrimesUpTo480)
  63.                         {
  64.                             if ((d == s1) || (d == c) || (d == b) || (d == a)) continue;
  65.                             foreach (var e in oddPrimesUpTo480)
  66.                             {
  67.                                 if ((e == s1) || (e == d) || (e == c) || (e == b) || (e == a)) continue;
  68.                                 foreach (var f in oddPrimesUpTo480)
  69.                                 {
  70.                                     var s2 = d + e + f;
  71.                                     if (!oddPrimesUpTo480.Contains(s2)) continue;
  72.                                     if ((s2 == a) || (s2 == b) || (s2 == c) || (s2 == d) || (s2 == e) || (s2 == f) || (s2 == s1)) continue;
  73.                                     if (s1 + s2 >= recordSum) continue;
  74.  
  75.                                     if ((f == s1) || (f == s2) || (f == e) || (f == d) || (f == c) || (f == b) || (f == a)) continue;
  76.                                     foreach (var g in oddPrimesUpTo480)
  77.                                     {
  78.                                         var s4 = a + d + g;
  79.                                         if (!oddPrimesUpTo480.Contains(s4)) continue;
  80.                                         if (s1 + s2 + s4 >= recordSum) continue;
  81.                                         if ((s4 == a) || (s4 == b) || (s4 == c) || (s4 == d) || (s4 == e) || (s4 == f) || (s4 == g) || (s4 == s1) || (s4 == s2)) continue;
  82.                                         var s7 = c + e + g;
  83.                                         if (!oddPrimesUpTo480.Contains(s7)) continue;
  84.                                         if (s1 + s2 + s4 + s7 >= recordSum) continue;
  85.                                         if ((s7 == a) || (s7 == b) || (s7 == c) || (s7 == d) || (s7 == e) || (s7 == f) || (s7 == g) || (s7 == s1) || (s7 == s2) || (s7 == s4)) continue;
  86.  
  87.                                         if ((g == s1) || (g == s2) || (g == s4) || (g == s7) || (g == f) || (g == e) || (g == d) || (g == c) || (g == b) || (g == a)) continue;
  88.                                         foreach (var h in oddPrimesUpTo480)
  89.                                         {
  90.                                             var s5 = b + e + h;
  91.                                             if (!oddPrimesUpTo480.Contains(s5)) continue;
  92.                                             if (s1 + s2 + s4 + s7 + s5 >= recordSum) continue;
  93.                                             if ((s5 == a) || (s5 == b) || (s5 == c) || (s5 == d) || (s5 == e) || (s5 == f) || (s5 == g) || (s5 == h) || (s5 == s1) || (s5 == s2) || (s5 == s4) || (s5 == s7)) continue;
  94.  
  95.                                             if ((h == s1) || (h == s2) || (h == s4) || (h == s7) || (h == s5) || (h == g) || (h == f) || (h == e) || (h == d) || (h == c) || (h == b) || (h == a)) continue;
  96.                                             foreach (var i in oddPrimesUpTo480)
  97.                                             {
  98.                                                 if ((i == s1) || (i == s2) || (i == s4) || (i == s7) || (i == s5) || (i == h) || (i == g) || (i == f) || (i == e) || (i == d) || (i == c) || (i == b) || (i == a)) continue;
  99.  
  100.                                                 var s3 = g + h + i;
  101.                                                 if (!oddPrimesUpTo480.Contains(s3)) continue;
  102.                                                 if (s1 + s2 + s4 + s7 + s5 + s3 >= recordSum) continue;
  103.                                                 if ((s3 == a) || (s3 == b) || (s3 == c) || (s3 == d) || (s3 == e) || (s3 == f) || (s3 == g) || (s3 == h) || (s3 == i) || (s3 == s1) || (s3 == s2) || (s3 == s4) || (s3 == s7) || (s3 == s5)) continue;
  104.                                                 var s6 = c + f + i;
  105.                                                 if (!oddPrimesUpTo480.Contains(s6)) continue;
  106.                                                 if (s1 + s2 + s4 + s7 + s5 + s3 + s6 >= recordSum) continue;
  107.                                                 if ((s6 == a) || (s6 == b) || (s6 == c) || (s6 == d) || (s6 == e) || (s6 == f) || (s6 == g) || (s6 == h) || (s6 == i) || (s6 == s1) || (s6 == s2) || (s6 == s4) || (s6 == s7) || (s6 == s5) || (s6 == s3)) continue;
  108.                                                 var s8 = a + e + i;
  109.                                                 if (!oddPrimesUpTo480.Contains(s8)) continue;
  110.                                                 if ((s8 == a) || (s8 == b) || (s8 == c) || (s8 == d) || (s8 == e) || (s8 == f) || (s8 == g) || (s8 == h) || (s8 == i) || (s8 == s1) || (s8 == s2) || (s8 == s4) || (s8 == s7) || (s8 == s5) || (s8 == s3) || (s8 == s6)) continue;
  111.  
  112.                                                 var totalsum = s1 + s2 + s3 + s4 + s5 + s6 + s7 + s8;
  113.                                                 if (totalsum < recordSum)
  114.                                                 {
  115.                                                     recordSum = totalsum;
  116.                                                     Console.WriteLine("---");
  117.                                                     Console.WriteLine("Sum of {0}:", totalsum);
  118.                                                     Console.WriteLine("    {0} {1} {2}|{3}", a, b, c, s1);
  119.                                                     Console.WriteLine("    {0} {1} {2}|{3}", d, e, f, s2);
  120.                                                     Console.WriteLine("    {0} {1} {2}|{3}", g, h, i, s3);
  121.                                                     Console.WriteLine("    -----------|---");
  122.                                                     Console.WriteLine("{0} {1} {2} {3}|{4}", s7, s4, s5, s6, s8);
  123.                                                     // If progress is showed, use this so you won't miss any solutions
  124.                                                     // Console.ReadKey();
  125.                                                 }
  126.                                             }
  127.                                         }
  128.                                     }
  129.                                 }
  130.                             }
  131.                         }
  132.                     }
  133.                 }
  134.             }
  135.  
  136.             Console.ReadKey();
  137.         }
  138.     }
  139. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top