How to resolve the algorithm Long primes step by step in the zkl programming language
How to resolve the algorithm Long primes step by step in the zkl 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 zkl programming language
Source code in the zkl programming language
var [const] BN=Import("zklBigNum"); // libGMP
primes,p := List.createLong(7_000), BN(3); // one big alloc vs lots of allocs
while(p.nextPrime()<=64_000){ primes.append(p.toInt()) } // 6412 of them, skipped 2
primes.append(p.toInt()); // and one more so tail prime is >64_000
longPrimes:=primes.filter(fcn(p){ findPeriod(p)==p-1 }); // yawn
fcn findPeriod(n){
r,period := 1,0;
do(n){ r=(10*r)%n }
rr:=r;
while(True){ // reduce is more concise but 2.5 times slower
r=(10*r)%n;
period+=1;
if(r==rr) break;
}
period
}
fiveHundred:=longPrimes.filter('<(500));
println("The long primes up to 500 are:\n",longPrimes.filter('<(500)).concat(","));
println("\nThe number of long primes up to:");
foreach n in (T(500, 1000, 2000, 4000, 8000, 16000, 32000, 64000)){
println(" %5d is %d".fmt( n, longPrimes.filter1n('>(n)) ));
}
You may also check:How to resolve the algorithm Sorting algorithms/Quicksort step by step in the TypeScript programming language
You may also check:How to resolve the algorithm Dot product step by step in the Elm programming language
You may also check:How to resolve the algorithm Roots of unity step by step in the Julia programming language
You may also check:How to resolve the algorithm Old lady swallowed a fly step by step in the Rust programming language
You may also check:How to resolve the algorithm Date manipulation step by step in the Java programming language