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

Published on 12 May 2024 09:40 PM
#Nim

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

Table of Contents

Problem Statement

A   long prime   (as defined here)   is a prime number whose reciprocal   (in decimal)   has a   period length   of one less than the prime number.

Long primes   are also known as:

Another definition:   primes   p   such that the decimal expansion of   1/p   has period   p-1,   which is the greatest period possible for any integer.

7   is the first long prime,   the reciprocal of seven is   1/7,   which is equal to the repeating decimal fraction   0.142857142857··· The length of the   repeating   part of the decimal fraction is six,   (the underlined part)   which is one less than the (decimal) prime number   7. Thus   7   is a long prime.

There are other (more) general definitions of a   long prime   which include wording/verbiage for bases other than ten.

Let's start with the solution:

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

Source code in the nim programming language

import strformat


func sieve(limit: int): seq[int] =

  var composite = newSeq[bool](limit + 1)
  var p = 3
  var p2 = p * p
  while p2 < limit:
    if not composite[p]:
      for n in countup(p2, limit, 2 * p):
        composite[n] = true
    inc p, 2
    p2 = p * p

  for n in countup(3, limit, 2):
    if not composite[n]:
      result.add n


func period(n: int): int =
  ## Find the period of the reciprocal of "n".
  var r = 1
  for i in 1..(n + 1):
    r = 10 * r mod n
  let r1 = r
  while true:
    r = 10 * r mod n
    inc result
    if r == r1: break


let primes = sieve(64000)
var longPrimes: seq[int]
for prime in primes:
  if prime.period() == prime - 1:
    longPrimes.add prime

const Numbers = [500, 1000, 2000, 4000, 8000, 16000, 32000, 64000]
var index, count = 0
var totals = newSeq[int](Numbers.len)
for longPrime in longPrimes:
  if longPrime > Numbers[index]:
    totals[index] = count
    inc index
  inc count
totals[^1] = count

echo &"The long primes up to {Numbers[0]} are:"
for i in 0..<totals[0]:
  stdout.write ' ', longPrimes[i]
stdout.write '\n'

echo "\nThe number of long primes up to:"
for i, total in totals:
  echo &"  {Numbers[i]:>5} is {total}"

You may also check:How to resolve the algorithm Currency step by step in the Tcl programming language
You may also check:How to resolve the algorithm Display an outline as a nested table step by step in the Go programming language
You may also check:How to resolve the algorithm Exponentiation operator step by step in the Objeck programming language
You may also check:How to resolve the algorithm Doubly-linked list/Element definition step by step in the Oforth programming language
You may also check:How to resolve the algorithm Fibonacci sequence step by step in the MAD programming language