How to resolve the algorithm Emirp primes step by step in the C# programming language

Published on 12 May 2024 09:40 PM
#C_Sharp

How to resolve the algorithm Emirp primes step by step in the C# programming language

Table of Contents

Problem Statement

An   emirp   (prime spelled backwards)   are primes that when reversed   (in their decimal representation)   are a different prime. (This rules out palindromic primes.)

In each list, the numbers should be in order. Invoke the (same) program once per task requirement, this will show what limit is used as the upper bound for calculating surplus (regular) primes. The specific method of how to determine if a range or if specific values are to be shown will be left to the programmer.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Emirp primes step by step in the C# programming language

The provided C# code is designed to find and display emirp primes within a specified limit and within a given range. Emirp primes are prime numbers that, when reversed, also form a prime number. Here's a breakdown of the code:

  1. Program Class:

    • The Program class serves as the entry point for the program and contains the static Main method.

  2. FindEmirpPrimes Method:

    • This method generates a sequence of emirp primes within a given limit.
    • It takes one parameter, limit, which specifies the upper bound for the search.
    • It uses two helper methods, Primes and Reverse, to determine whether a number is a prime and reverse it, respectively.

  3. Primes Method:

    • This method yields prime numbers up to the specified bound.
    • It uses the Sieve of Eratosthenes algorithm to efficiently find primes.

  4. Reverse Method:

    • This extension method reverses a given int.
    • It handles negative numbers and employs a loop to reverse the digits.

  5. Extensions Class:

    • This class contains various extension methods:
      • ToHashSet<T>: Converts an IEnumerable<T> to a HashSet<T>.
      • Delimit<T>: Joins an IEnumerable<T> into a string, with an optional separator.

  6. Main Method:

    • The Main method is the starting point of the program and serves as the user interface.
    • It sets the limit for finding emirp primes to 1,000,000.
    • It prints the first 20 emirp primes, the emirp primes between 7700 and 8000, and the 10,000th emirp prime.

In summary, this code finds and displays emirp primes within a specified limit, providing a demonstration of prime number properties and the use of efficient algorithms and extension methods.

Source code in the csharp programming language

using static System.Console;
using System;
using System.Linq;
using System.Collections.Generic;

public class Program
{
    public static void Main() {
        const int limit = 1_000_000;
        WriteLine("First 20:");
        WriteLine(FindEmirpPrimes(limit).Take(20).Delimit());
        WriteLine();
		
        WriteLine("Between 7700 and 8000:");
        WriteLine(FindEmirpPrimes(limit).SkipWhile(p => p < 7700).TakeWhile(p => p < 8000).Delimit());
        WriteLine();
		
        WriteLine("10000th:");
        WriteLine(FindEmirpPrimes(limit).ElementAt(9999));
    }
	
    private static IEnumerable<int> FindEmirpPrimes(int limit)
    {
        var primes = Primes(limit).ToHashSet();
		
        foreach (int prime in primes) {
            int reverse = prime.Reverse();
            if (reverse != prime && primes.Contains(reverse)) yield return prime;
	}
    }
	
    private static IEnumerable<int> Primes(int bound) {
        if (bound < 2) yield break;
        yield return 2;
		
        BitArray composite = new BitArray((bound - 1) / 2);
        int limit = ((int)(Math.Sqrt(bound)) - 1) / 2;
        for (int i = 0; i < limit; i++) {
            if (composite[i]) continue;
	    int prime = 2 * i + 3;
	    yield return prime;
			
	    for (int j = (prime * prime - 2) / 2; j < composite.Count; j += prime)
	        composite[j] = true;
        }
	for (int i = limit; i < composite.Count; i++)
	    if (!composite[i]) yield return 2 * i + 3;
    }
}

public static class Extensions
{
    public static HashSet<T> ToHashSet<T>(this IEnumerable<T> source) => new HashSet<T>(source);

    private const string defaultSeparator = " ";
    public static string Delimit<T>(this IEnumerable<T> source, string separator = defaultSeparator) =>
        string.Join(separator ?? defaultSeparator, source);

    public static int Reverse(this int number)
    {
	if (number < 0) return -Reverse(-number);
	if (number < 10) return number;
	int reverse = 0;
	while (number > 0) {
	    reverse = reverse * 10 + number % 10;
	    number /= 10;
	}
	return reverse;
    }
}

You may also check:How to resolve the algorithm Pythagorean quadruples step by step in the ALGOL 68 programming language
You may also check:How to resolve the algorithm Move-to-front algorithm step by step in the Quackery programming language
You may also check:How to resolve the algorithm Program termination step by step in the Bracmat programming language
You may also check:How to resolve the algorithm Determine if a string has all unique characters step by step in the PicoLisp programming language
You may also check:How to resolve the algorithm Knapsack problem/Unbounded step by step in the JavaScript programming language