How to resolve the algorithm Fermat pseudoprimes step by step in the Nim programming language

Published on 12 May 2024 09:40 PM
#Nim

How to resolve the algorithm Fermat pseudoprimes step by step in the Nim programming language

Table of Contents

Problem Statement

A Fermat pseudoprime is a positive composite integer that passes the Fermat primality test. Fermat's little theorem states that if p is prime and a is coprime to p, then ap−1 − 1 is divisible by p. For an integer a > 1, if a composite integer x evenly divides ax−1 − 1, then x is called a Fermat pseudoprime to base a. Fermat pseudoprimes to base 2 are sometimes called Sarrus numbers or Poulet numbers. Fermat pseudoprimes can be found to any positive integer base. When using a base integer a = 1, this method returns all composite numbers.

For base integers a of 1 through 20:

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Fermat pseudoprimes step by step in the Nim programming language

Source code in the nim programming language

import std/[strformat, strutils]

proc powMod*(a, n, m: int): int =
  ## Return "a^n mod m".
  var a = a mod m
  var n = n
  if a > 0:
    result = 1
    while n > 0:
      if (n and 1) != 0:
        result = (result * a) mod m
      n = n shr 1
      a = (a * a) mod m

func isPrime(n: Natural): bool =
  ## Return true if "n" is prime.
  if n < 2: return false
  if (n and 1) == 0: return n == 2
  if n mod 3 == 0: return n == 3
  var k = 5
  var delta = 2
  while k * k <= n:
    if n mod k == 0: return false
    inc k, delta
    delta = 6 - delta
  result = true

func isFermatPseudoprime(x, a: int): bool =
  ## Return true is "x" is a Fermat pseudoprime to base "a".
  if x.isPrime: return false
  result = powMod(a, x - 1, x) == 1

const Lim = 50_000

for a in 1..20:
  var count = 0
  var first20: seq[int]
  for x in 1..Lim:
    if x.isFermatPseudoprime(a):
      inc count
      if count <= 20:
        first20.add x
  echo &"Base {a}:"
  echo &"  Number of Fermat pseudoprimes up to {insertSep($Lim)}: {count}"
  echo &"  First 20: {first20.join(\" \")}"

You may also check:How to resolve the algorithm Here document step by step in the SQL PL programming language
You may also check:How to resolve the algorithm Hamming numbers step by step in the Elixir programming language
You may also check:How to resolve the algorithm Sort stability step by step in the R programming language
You may also check:How to resolve the algorithm User input/Text step by step in the JavaScript programming language
You may also check:How to resolve the algorithm Apply a callback to an array step by step in the Frink programming language