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

Published on 12 May 2024 09:40 PM
#Xbasic

How to resolve the algorithm Long primes step by step in the XBasic 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 XBasic programming language

Source code in the xbasic programming language

PROGRAM "longprimes"
VERSION "0.0002"

DECLARE FUNCTION Entry()
INTERNAL FUNCTION Sieve(limit&, primes&[], count%)
INTERNAL FUNCTION FindPeriod(n&)

FUNCTION Entry()
  DIM numbers&[7]
  numbers&[0] = 500
  numbers&[1] = 1000
  numbers&[2] = 2000
  numbers&[3] = 4000
  numbers&[4] = 8000
  numbers&[5] = 16000
  numbers&[6] = 32000
  numbers&[7] = 64000
  numberUpperBound% = UBOUND(numbers&[])
  DIM totals%[numberUpperBound%]
  DIM primes&[6499]
  PRINT "Please wait."
  PRINT
  Sieve(64000, @primes&[], @primeCount%)
  DIM longPrimes&[primeCount% - 1] ' Surely longCount% < primeCount%
  longCount% = 0
  FOR i% = 0 TO primeCount% - 1
    prime& = primes&[i%]
    IF FindPeriod(prime&) = prime& - 1 THEN
      longPrimes&[longCount%] = prime&
      INC longCount%
    END IF
  NEXT i%
  count% = 0
  index% = 0
  FOR i% = 0 TO longCount% - 1
    IF longPrimes&[i%] > numbers&[index%] THEN
      totals%[index%] = count%
      INC index%
    END IF
    INC count%
  NEXT i%
  totals%[numberUpperBound%] = count%
  PRINT "The long primes up to"; numbers&[0]; " are:"
  PRINT "[";
  FOR i% = 0 TO totals%[0] - 2
    PRINT STRING$(longPrimes&[i%]); " ";
  NEXT i%
  IF totals%[0] > 0 THEN
    PRINT STRING$(longPrimes&[totals%[0] - 1]);
  END IF
  PRINT "]"
  PRINT
  PRINT "The number of long primes up to:"
  FOR i% = 0 TO numberUpperBound%
    PRINT FORMAT$("  #####", numbers&[i%]); " is"; totals%[i%]
  NEXT i%
END FUNCTION

FUNCTION Sieve(limit&, primes&[], count%)
  DIM c@[limit&]
  FOR i& = 0 TO limit&
    c@[i&] = 0
  NEXT i&
  ' No need to process even numbers
  p% = 3
  n% = 0
  p2& = p% * p%
  DO WHILE p2& <= limit&
    FOR i& = p2& TO limit& STEP 2 * p%
      c@[i&] = 1
    NEXT i&
    DO
      p% = p% + 2
    LOOP UNTIL !c@[p%]
    p2& = p% * p%
  LOOP
  FOR i& = 3 TO limit& STEP 2
    IFZ c@[i&] THEN
      primes&[n%] = i&
      INC n%
    END IF
  NEXT i&
  count% = n%
END FUNCTION

' Finds the period of the reciprocal of n&
FUNCTION FindPeriod(n&)
  r& = 1
  period& = 0
  FOR i& = 1 TO n& + 1
    r& = (10 * r&) MOD n&
  NEXT i&
  rr& = r&
  DO
    r& = (10 * r&) MOD n&
    INC period&
  LOOP UNTIL r& = rr&
END FUNCTION period&

END PROGRAM

You may also check:How to resolve the algorithm Loop over multiple arrays simultaneously step by step in the Insitux programming language
You may also check:How to resolve the algorithm Execute Computer/Zero step by step in the RPL programming language
You may also check:How to resolve the algorithm Combinations step by step in the Oz programming language
You may also check:How to resolve the algorithm Loop over multiple arrays simultaneously step by step in the EchoLisp programming language
You may also check:How to resolve the algorithm String length step by step in the Yorick programming language