How to resolve the algorithm Wieferich primes step by step in the Forth programming language

Published on 12 May 2024 09:40 PM
#Forth

How to resolve the algorithm Wieferich primes step by step in the Forth programming language

Table of Contents

Problem Statement

In number theory, a Wieferich prime is a prime number p such that p2 evenly divides 2(p − 1) − 1 .

It is conjectured that there are infinitely many Wieferich primes, but as of March 2021,only two have been identified.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Wieferich primes step by step in the Forth programming language

Source code in the forth programming language

: prime? ( n -- ? ) here + c@ 0= ;
: notprime! ( n -- ) here + 1 swap c! ;

: prime_sieve { n -- }
  here n erase
  0 notprime!
  1 notprime!
  n 4 > if
    n 4 do i notprime! 2 +loop
  then
  3
  begin
    dup dup * n <
  while
    dup prime? if
      n over dup * do
        i notprime!
      dup 2* +loop
    then
    2 +
  repeat
  drop ;

: modpow { c b a -- a^b mod c }
  c 1 = if 0 exit then
  1
  a c mod to a
  begin
    b 0>
  while
    b 1 and 1 = if
      a * c mod
    then
    a a * c mod to a
    b 2/ to b
  repeat ;

: wieferich_prime? { p -- ? }
  p prime? if
    p p * p 1- 2 modpow 1 =
  else
    false
  then ;  

: wieferich_primes { n -- }
  ." Wieferich primes less than " n 1 .r ." :" cr
  n prime_sieve
  n 0 do
    i wieferich_prime? if
      i 1 .r cr
    then
  loop ;

5000 wieferich_primes
bye

You may also check:How to resolve the algorithm Averages/Arithmetic mean step by step in the Joy programming language
You may also check:How to resolve the algorithm Palindrome detection step by step in the PARI/GP programming language
You may also check:How to resolve the algorithm Read entire file step by step in the AutoHotkey programming language
You may also check:How to resolve the algorithm History variables step by step in the Clojure programming language
You may also check:How to resolve the algorithm Sorting algorithms/Bubble sort step by step in the Python programming language