How to resolve the algorithm Truncatable primes step by step in the Nim programming language

Published on 12 May 2024 09:40 PM
#Nim

How to resolve the algorithm Truncatable primes step by step in the Nim programming language

Table of Contents

Problem Statement

A truncatable prime is a prime number that when you successively remove digits from one end of the prime, you are left with a new prime number.

The number 997 is called a left-truncatable prime as the numbers 997, 97, and 7 are all prime. The number 7393 is a right-truncatable prime as the numbers 7393, 739, 73, and 7 formed by removing digits from its right are also prime. No zeroes are allowed in truncatable primes.

The task is to find the largest left-truncatable and right-truncatable primes less than one million (base 10 is implied).

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Truncatable primes step by step in the Nim programming language

Source code in the nim programming language

import sets, strutils, algorithm
 
proc primes(n: int64): seq[int64] =
  var multiples: HashSet[int64]
  for i in 2..n:
    if i notin multiples:
      result.add i
      for j in countup(i*i, n, i.int):
        multiples.incl j
 
proc truncatablePrime(n: int64): tuple[left, right: int64] =
  var
    primelist: seq[string]
  for x in primes(n):
    primelist.add($x)
  reverse primelist
  var primeset = primelist.toHashSet
  for n in primelist:
    var alltruncs: HashSet[string]
    for i in 0..n.high:
      alltruncs.incl n[i..n.high]
    if alltruncs <= primeset:
      result.left = parseInt(n)
      break
  for n in primelist:
    var alltruncs: HashSet[string]
    for i in 0..n.high:
      alltruncs.incl n[0..i]
    if alltruncs <= primeset:
      result.right = parseInt(n)
      break
 
echo truncatablePrime(1000000i64)

You may also check:How to resolve the algorithm Base64 decode data step by step in the JavaScript programming language
You may also check:How to resolve the algorithm Semiprime step by step in the Python programming language
You may also check:How to resolve the algorithm FizzBuzz step by step in the Oberon-2 programming language
You may also check:How to resolve the algorithm Universal Turing machine step by step in the 11l programming language
You may also check:How to resolve the algorithm Sorting algorithms/Shell sort step by step in the XPL0 programming language