Discussion on: Write a script to find permutable prime numbers

[Sung M. Kim]

Pretty long compared to the Python version by Florian Rohrer.

It uses Sieve of Eratosthenes to generate prime numbers up to 1000.
Then just compares if all permutations of each prime number are in the prime set.

The main method that does the job is GetPermutablePrimes.

using System.Collections.Generic;
using System.Linq;
using Xunit;

namespace Demo.LearnByDoing.Tests.RandomStuff
{
    /// <summary>
    /// https://dev.to/peter/write-a-script-to-find-permutable-prime-numbers-1gg0
    /// </summary>
    public class PermutablePrimesTest
    {
        private const int UPTO = 1000;

        [Fact]
        public void TestSieveOf()
        {
            var expected = new[]
                {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61
                , 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139
                , 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229
                , 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317
                , 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421
                , 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521
                , 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619
                , 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733
                , 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839
                , 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953
                , 967, 971, 977, 983, 991, 997};
            var actual = GetPrimeNumbers(UPTO).ToList();

            Assert.True(expected.SequenceEqual(actual));
        }

        [Fact]
        public void TestPermutablePrimes()
        {
            var expected = new[] {2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97, 113, 131, 199, 311, 337, 373, 733, 919, 991};
            var actual = GetPermutablePrimes(UPTO).ToList();
            Assert.True(expected.SequenceEqual(actual));
        }

        private IEnumerable<int> GetPermutablePrimes(int upto)
        {
            // For O(1) lookup
            var primes = new HashSet<int>(GetPrimeNumbers(upto));

            foreach (var prime in primes)
            {
                List<int> perms = GetPermutations(prime.ToString()).ToList();
                if (perms.All(perm => primes.Contains(perm))) yield return prime;
            }
        }

        private IEnumerable<int> GetPermutations(string input)
        {
            return FillPermutations(input).Select(int.Parse);
        }

        private IEnumerable<string> FillPermutations(string input)
        {
            if (input.Length == 1) yield return input;
            else if (input.Length == 2)
            {
                yield return input;
                yield return new string(new[] { input[1], input[0] });
            }
            else
            {
                for (int i = 0; i < input.Length; i++)
                {
                    string prefix = input[i].ToString();
                    string left = input.Substring(0, i);
                    string right = input.Substring(i + 1);
                    string newInput = left + right;

                    foreach (var rest in FillPermutations(newInput))
                    {
                        yield return prefix + rest;
                    }
                }
            }
        }

        private IEnumerable<int> GetPrimeNumbers(int upto)
        {
            // Initialize all numbers as true to "upto + 1" since array is 0-based.
            var primes = Enumerable.Repeat(true, upto + 1).ToArray();

            for (int i = 2; i * i <= upto; i++)
            {
                // It's already processed.
                if (!primes[i]) continue;

                for (int j = i * 2; j <= upto; j += i)
                {
                    primes[j] = false;
                }
            }

            // Skip 0 & 1
            // Return indexes, which are prime numbers
            const int skipBy = 2;
            return primes
                .Skip(skipBy)
                .Select((_, i) => new { IsPrime = _, Value = i + skipBy })
                .Where(obj => obj.IsPrime)
                .Select(obj => obj.Value);
        }
    }
}