Rosetta Code

Long primes: Difference between revisions

Page Discussion

Long primes (view source)

Revision as of 14:24, 7 January 2024

10,899 bytes added ,  4 months ago
Added Algol 68
(Added Algol 68)
 
(16 intermediate revisions by 7 users not shown)
Line 55:
{{trans|Python}}
 
<langsyntaxhighlight lang="11l">F sieve(limit)
[Int] primes
V c = [0B] * (limit + 1)
Line 107:
print("\nThe number of long primes up to:")
L(total) totals
print(‘ #5 is #.’.format(numbers[L.index], total))</langsyntaxhighlight>
 
{{out}}
Line 123:
32000 is 1300
64000 is 2430
</pre>
 
=={{header|ALGOL 68}}==
The PERIOD operator is translated from the C sample's find_period routine.
<syntaxhighlight lang="algol68">
BEGIN # find some long primes - primes whose reciprocol have a period of p-1 #
INT max number = 64 000;
# sieve the primes to max number #
[ 1 : max number ]BOOL is prime; FOR i TO UPB is prime DO is prime[ i ] := ODD i OD;
is prime[ 1 ] := FALSE;
is prime[ 2 ] := TRUE;
FOR s FROM 3 BY 2 TO ENTIER sqrt( max number ) DO
IF is prime[ s ] THEN
FOR p FROM s * s BY s TO UPB is prime DO is prime[ p ] := FALSE OD
FI
OD;
 
OP PERIOD = ( INT n )INT: # returns the period of the reciprocal of n #
BEGIN
INT r := 1;
FOR i TO n + 1 DO
r *:= 10 MODAB n
OD;
INT rr = r;
INT period := 0;
WHILE r *:= 10 MODAB n;
period +:= 1;
r /= rr
DO SKIP OD;
period
END # PERIOD # ;
 
print( ( "Long primes upto 500:", newline, " " ) );
INT lp count := 0;
FOR p FROM 3 TO 500 DO
IF is prime[ p ] THEN
IF PERIOD p = p - 1 THEN
print( ( " ", whole( p, 0 ) ) );
lp count +:= 1
FI
FI
OD;
print( ( newline ) );
INT limit := 500;
FOR p FROM 500 WHILE limit <= 64 000 DO
IF p = limit THEN
print( ( "Long primes up to: ", whole( p, -5 ), ": ", whole( lp count, 0 ), newline ) );
limit *:= 2
FI;
IF is prime[ p ] THEN
IF PERIOD p = p - 1 THEN
lp count +:= 1
FI
FI
OD
 
END
</syntaxhighlight>
{{out}}
<pre>
Long primes upto 500:
7 17 19 23 29 47 59 61 97 109 113 131 149 167 179 181 193 223 229 233 257 263 269 313 337 367 379 383 389 419 433 461 487 491 499
Long primes up to: 500: 35
Long primes up to: 1000: 60
Long primes up to: 2000: 116
Long primes up to: 4000: 218
Long primes up to: 8000: 390
Long primes up to: 16000: 716
Long primes up to: 32000: 1300
Long primes up to: 64000: 2430
</pre>
 
Line 128 ⟶ 198:
The isLongPrime(n) handler here is a translation of the faster [https://www.rosettacode.org/wiki/Long_primes#Phix Phix] one.
 
<langsyntaxhighlight lang="applescript">on sieveOfEratosthenes(limit)
script o
property numberList : {missing value}
Line 234 ⟶ 304:
end longPrimesTask
 
longPrimesTask()</langsyntaxhighlight>
 
{{output}}
Line 250 ⟶ 320:
=={{header|C}}==
{{trans|Go}}
<langsyntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
Line 330 ⟶ 400:
free(primes);
return 0;
}</langsyntaxhighlight>
 
{{out}}
Line 350 ⟶ 420:
=={{header|C sharp}}==
{{works with|C sharp|7}}
<langsyntaxhighlight lang="csharp">using System;
using System.Collections.Generic;
using System.Linq;
Line 392 ⟶ 462:
for (; j<= lim; j++) if (!flags[j]) yield return j;
}
}</langsyntaxhighlight>
{{out}}
<pre>
Line 407 ⟶ 477:
=={{header|C++}}==
{{trans|C}}
<langsyntaxhighlight lang="cpp">
#include <iomanip>
#include <iostream>
Line 494 ⟶ 564:
delete [] totals;
}
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 515 ⟶ 585:
=={{header|Common Lisp}}==
{{trans|Raku}}
<langsyntaxhighlight lang="lisp">; Primality test using the Sieve of Eratosthenes with a couple minor optimizations
(defun primep (n)
(cond ((and (<= n 3) (> n 1)) t)
Line 541 ⟶ 611:
 
(format t "~{~a~^, ~}" (loop for n from 1 to 500 if (long-prime-p n) collect n))
</syntaxhighlight>
</lang>
{{Out}}
<pre>7, 17, 19, 23, 29, 47, 59, 61, 97, 109, 113, 131, 149, 167, 179, 181, 193, 223, 229, 233, 257, 263, 269, 313, 337, 367, 379, 383, 389, 419, 433, 461, 487, 491, 499</pre>
Line 548 ⟶ 618:
{{trans|Sidef}}
Simpler but slower.
<langsyntaxhighlight lang="ruby">require "big"
 
def prime?(n) # P3 Prime Generator primality test
Line 578 ⟶ 648:
puts "Number of long primes ≤ #{n}: #{(7..n).count { |pc| long_prime? pc }}"
end
puts "\nTime: #{(Time.monotonic - start).total_seconds} secs"</langsyntaxhighlight>
 
{{out}}
Line 598 ⟶ 668:
 
Faster: using divisors of (p - 1) and powmod().
<langsyntaxhighlight lang="ruby">require "big"
 
def prime?(n) # P3 Prime Generator primality test
Line 643 ⟶ 713:
puts "Number of long primes ≤ #{n}: #{(7..n).count { |pc| long_prime? pc }}"
end
puts "\nTime: #{(Time.monotonic - start).total_seconds} secs"</langsyntaxhighlight>
{{out}}
<pre>
Line 663 ⟶ 733:
=={{header|Delphi}}==
See [https://rosettacode.org/wiki/Long_primes#Pascal Pascal].
 
 
=={{header|EasyLang}}==
<syntaxhighlight>
fastfunc isprim num .
if num mod 2 = 0 and num > 2
return 0
.
i = 3
while i <= sqrt num
if num mod i = 0
return 0
.
i += 2
.
return 1
.
prim = 2
proc nextprim . .
repeat
prim += 1
until isprim prim = 1
.
.
func period n .
r = 1
repeat
r = (r * 10) mod n
p += 1
until r <= 1
.
return p
.
#
print "Long primes up to 500 are:"
repeat
nextprim
until prim > 500
if period prim = prim - 1
write prim & " "
cnt += 1
.
.
print ""
print ""
print "The number of long primes up to:"
limit = 500
repeat
if prim > limit
print limit & " is " & cnt
limit *= 2
.
until limit > 32000
if period prim = prim - 1
cnt += 1
.
nextprim
.
</syntaxhighlight>
 
=={{header|F_Sharp|F#}}==
Line 668 ⟶ 797:
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_function Extensible Prime Generator (F#)]<br>
This task uses [[Factors_of_an_integer#F.23]]
<langsyntaxhighlight lang="fsharp">
// Return true if prime n is a long prime. Nigel Galloway: September 25th., 2018
let fN n g = let rec fN i g e l = match e with | 0UL -> i
Line 675 ⟶ 804:
fN 1UL 10UL (uint64 g) (uint64 n)
let isLongPrime n=Seq.length (factors (n-1) |> Seq.filter(fun g->(fN n g)=1UL))=1
</syntaxhighlight>
</lang>
===The Task===
<langsyntaxhighlight lang="fsharp">
primes |> Seq.skip 3 |> Seq.takeWhile(fun n->n<500) |> Seq.filter isLongPrime |> Seq.iter(printf "%d ")
</syntaxhighlight>
</lang>
{{out}}
<pre>
7 17 19 23 29 47 59 61 97 109 113 131 149 167 179 181 193 223 229 233 257 263 269 313 337 367 379 383 389 419 433 461 487 491 499
</pre>
<langsyntaxhighlight lang="fsharp">
printfn "There are %d long primes less than 500" (primes |> Seq.skip 3 |> Seq.takeWhile(fun n->n<500) |> Seq.filter isLongPrime |> Seq.length)
</syntaxhighlight>
</lang>
{{out}}
<pre>
There are 35 long primes less than 500
</pre>
<langsyntaxhighlight lang="fsharp">
printfn "There are %d long primes less than 1000" (primes |> Seq.skip 3 |> Seq.takeWhile(fun n->n<1000) |> Seq.filter isLongPrime |> Seq.length)
</syntaxhighlight>
</lang>
{{out}}
<pre>
There are 60 long primes less than 1000
</pre>
<langsyntaxhighlight lang="fsharp">
printfn "There are %d long primes less than 2000" (primes |> Seq.skip 3 |> Seq.takeWhile(fun n->n<2000) |> Seq.filter isLongPrime |> Seq.length)
</syntaxhighlight>
</lang>
{{out}}
<pre>
There are 116 long primes less than 2000
</pre>
<langsyntaxhighlight lang="fsharp">
printfn "There are %d long primes less than 4000" (primes |> Seq.skip 3 |> Seq.takeWhile(fun n->n<4000) |> Seq.filter isLongPrime|> Seq.length)
</syntaxhighlight>
</lang>
{{out}}
<pre>
There are 218 long primes less than 4000
</pre>
<langsyntaxhighlight lang="fsharp">
printfn "There are %d long primes less than 8000" (primes |> Seq.skip 3 |> Seq.takeWhile(fun n->n<8000) |> Seq.filter isLongPrime |> Seq.length)
</syntaxhighlight>
</lang>
{{out}}
<pre>
There are 390 long primes less than 8000
</pre>
<langsyntaxhighlight lang="fsharp">
printfn "There are %d long primes less than 16000" (primes |> Seq.skip 3 |> Seq.takeWhile(fun n->n<16000) |> Seq.filter isLongPrime |> Seq.length)
</syntaxhighlight>
</lang>
{{out}}
<pre>
There are 716 long primes less than 16000
</pre>
<langsyntaxhighlight lang="fsharp">
printfn "There are %d long primes less than 32000" (primes |> Seq.skip 3 |> Seq.takeWhile(fun n->n<32000) |> Seq.filter isLongPrime |> Seq.length)
</syntaxhighlight>
</lang>
{{out}}
<pre>
There are 1300 long primes less than 32000
</pre>
<langsyntaxhighlight lang="fsharp">
printfn "There are %d long primes less than 64000" (primes |> Seq.skip 3 |> Seq.takeWhile(fun n->n<64000) |> Seq.filter isLongPrime|> Seq.length)
</syntaxhighlight>
</lang>
{{out}}
<pre>
There are 2430 long primes less than 64000
</pre>
<langsyntaxhighlight lang="fsharp">
printfn "There are %d long primes less than 128000" (primes |> Seq.skip 3 |> Seq.takeWhile(fun n->n<128000) |> Seq.filter isLongPrime|> Seq.length)
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 748 ⟶ 877:
Real: 00:00:01.294, CPU: 00:00:01.300, GC gen0: 27, gen1: 0
</pre>
<langsyntaxhighlight lang="fsharp">
printfn "There are %d long primes less than 256000" (primes |> Seq.skip 3 |> Seq.takeWhile(fun n->n<256000) |> Seq.filter isLongPrime|> Seq.length)
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 756 ⟶ 885:
Real: 00:00:03.434, CPU: 00:00:03.440, GC gen0: 58, gen1: 0
</pre>
<langsyntaxhighlight lang="fsharp">
printfn "There are %d long primes less than 512000" (primes |> Seq.skip 3 |> Seq.takeWhile(fun n->n<512000) |> Seq.filter isLongPrime|> Seq.length)
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 764 ⟶ 893:
Real: 00:00:09.248, CPU: 00:00:09.260, GC gen0: 128, gen1: 0
</pre>
<langsyntaxhighlight lang="fsharp">
printfn "There are %d long primes less than 1024000" (primes |> Seq.skip 3 |> Seq.takeWhile(fun n->n<1024000) |> Seq.filter isLongPrime|> Seq.length)
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 774 ⟶ 903:
 
=={{header|Factor}}==
<langsyntaxhighlight lang="factor">USING: formatting fry io kernel math math.functions math.primes
math.primes.factors memoize prettyprint sequences ;
IN: rosetta-code.long-primes
Line 796 ⟶ 925:
[ .#lp<=n ] each ;
 
MAIN: long-primes-demo</langsyntaxhighlight>
{{out}}
<pre>
Line 815 ⟶ 944:
{{works with|Gforth}}
The prime sieve code was borrowed from [[Sieve of Eratosthenes#Forth]].
<langsyntaxhighlight lang="forth">: prime? ( n -- ? ) here + c@ 0= ;
: notprime! ( n -- ) here + 1 swap c! ;
 
Line 904 ⟶ 1,033:
 
main
bye</langsyntaxhighlight>
 
{{out}}
Line 925 ⟶ 1,054:
 
=={{header|FreeBASIC}}==
<langsyntaxhighlight lang="freebasic">' version 01-02-2019
' compile with: fbc -s console
 
Line 999 ⟶ 1,128:
Print : Print "hit any key to end program"
Sleep
End</langsyntaxhighlight>
{{out}}
<pre>Long primes upto 500 are 7 17 19 23 29 47 59 61 97 109 113 131 149 167 179 181 193 223 229 233 257 263 269 313 337 367 379 383 389 419 433 461 487 491 499
Line 1,013 ⟶ 1,142:
 
=={{header|Go}}==
<langsyntaxhighlight lang="go">package main
import "fmt"
Line 1,082 ⟶ 1,211:
fmt.Printf(" %5d is %d\n", numbers[i], total)
}
}</langsyntaxhighlight>
 
{{out}}
Line 1,100 ⟶ 1,229:
</pre>
=={{header|Haskell}}==
<langsyntaxhighlight Haskelllang="haskell">import Data.List (elemIndex)
 
longPrimesUpTo :: Int -> [Int]
Line 1,137 ⟶ 1,266:
)
putStrLn ("500 is " <> show (length fiveHundred))
display 1000</langsyntaxhighlight>
{{out}}
<pre>The long primes up to 35 are:
Line 1,199 ⟶ 1,328:
=={{header|Java}}==
{{trans|C}}
<langsyntaxhighlight lang="java">
import java.util.LinkedList;
import java.util.List;
Line 1,269 ⟶ 1,398:
}
}
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 1,297 ⟶ 1,426:
 
'''Preliminaries'''
<syntaxhighlight lang="jq">
<lang jq>
def count(s): reduce s as $x (0; .+1);
 
Line 1,329 ⟶ 1,458:
2, 3, ([2,3] | next);
 
</syntaxhighlight>
</lang>
'''Long Primes'''
<syntaxhighlight lang="jq">
<lang jq>
# finds the period of the reciprocal of .
# (The following definition does not make a special case of 2
Line 1,365 ⟶ 1,494:
| "Number of long primes ≤ \(.): \(count_long_primes)" )
 
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 1,417 ⟶ 1,546:
=={{header|Julia}}==
{{trans|Sidef}}
<langsyntaxhighlight lang="julia">
using Primes
 
Line 1,448 ⟶ 1,577:
println("Number of long primes ≤ $i: $(sum(map(x->islongprime(x), 1:i)))")
end
</syntaxhighlight>
</lang>
{{output}}<pre>
Long primes ≤ 500:
Line 1,466 ⟶ 1,595:
=={{header|Kotlin}}==
{{trans|Go}}
<langsyntaxhighlight lang="scala">// Version 1.2.60
fun sieve(limit: Int): List<Int> {
Line 1,526 ⟶ 1,655:
System.out.printf(" %5d is %d\n", numbers[i], total)
}
}</langsyntaxhighlight>
 
{{output}}
Line 1,548 ⟶ 1,677:
Sieve leave to stack of values primes. This happen because we call the function as a module, so we pass the current stack (modules call modules passing own stack of values). We can place value to stack using Push to the top (as LIFO) or using Data to bottom (as FIFO). Variable Number read a number from stack and drop it.
 
<syntaxhighlight lang="m2000 interpreter">
<lang M2000 Interpreter>
Module LongPrimes {
Sieve=lambda (limit)->{
Line 1,618 ⟶ 1,747:
}
LongPrimes
</syntaxhighlight>
</lang>
 
{{out}}
Line 1,637 ⟶ 1,766:
 
=={{header|Maple}}==
<syntaxhighlight lang="maple">
<lang Maple>
with(NumberTheory):
with(ArrayTools):
Line 1,672 ⟶ 1,801:
numOfLongPrimes;
 
</syntaxhighlight>
</lang>
{{out}}<pre>
[7, 17, 19, 23, 29, 47, 59, 61, 97, 109, 113, 131, 149, 167, 179, 181, 193,
Line 1,684 ⟶ 1,813:
 
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<langsyntaxhighlight Mathematicalang="mathematica">lPrimes[n_] := Select[Range[2, n], Length[RealDigits[1/#][[1, 1]]] == # - 1 &];
lPrimes[500]
Length /@ lPrimes /@ ( 250*2^Range[8])</langsyntaxhighlight>
{{out}}
<pre>{7, 17, 19, 23, 29, 47, 59, 61, 97, 109, 113, 131, 149, 167, 179,
Line 1,693 ⟶ 1,822:
 
{35, 60, 116, 218, 390, 716, 1300, 2430}
</pre>
 
=={{header|Maxima}}==
<syntaxhighlight lang="maxima">
/* Test cases */
/* Long primes up to 500 */
sublist(makelist(i,i,500),lambda([x],primep(x) and zn_order(10,x)=x-1));
 
/* Number of long primes up to a specified limit */
length(sublist(makelist(i,i,500),lambda([x],primep(x) and zn_order(10,x)=x-1)));
length(sublist(makelist(i,i,1000),lambda([x],primep(x) and zn_order(10,x)=x-1)));
length(sublist(makelist(i,i,2000),lambda([x],primep(x) and zn_order(10,x)=x-1)));
length(sublist(makelist(i,i,4000),lambda([x],primep(x) and zn_order(10,x)=x-1)));
length(sublist(makelist(i,i,8000),lambda([x],primep(x) and zn_order(10,x)=x-1)));
length(sublist(makelist(i,i,16000),lambda([x],primep(x) and zn_order(10,x)=x-1)));
length(sublist(makelist(i,i,32000),lambda([x],primep(x) and zn_order(10,x)=x-1)));
length(sublist(makelist(i,i,64000),lambda([x],primep(x) and zn_order(10,x)=x-1)));
</syntaxhighlight>
{{out}}
<pre>
[7,17,19,23,29,47,59,61,97,109,113,131,149,167,179,181,193,223,229,233,257,263,269,313,337,367,379,383,389,419,433,461,487,491,499]
 
35
60
116
218
390
716
1300
2430
</pre>
 
=={{header|NewLISP}}==
<syntaxhighlight lang="newlisp">
<lang NewLISP>
;;; Using the fact that 10 has to be a primitive root mod p
;;; for p to be a reptend/long prime.
Line 1,724 ⟶ 1,883:
(println (find-reptends 500))
(println (map (fn(n) (println n " --> " (length (find-reptends n)))) '(500 1000 2000 4000 8000 16000 32000 64000)))
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 1,740 ⟶ 1,899:
=={{header|Nim}}==
{{trans|Kotlin}}
<langsyntaxhighlight Nimlang="nim">import strformat
 
 
Line 1,795 ⟶ 1,954:
echo "\nThe number of long primes up to:"
for i, total in totals:
echo &" {Numbers[i]:>5} is {total}"</langsyntaxhighlight>
 
{{out}}
Line 1,815 ⟶ 1,974:
www . arndt-bruenner.de/mathe/scripts/periodenlaenge.htm
 
<langsyntaxhighlight lang="pascal">
program Periode;
 
Line 2,258 ⟶ 2,417:
F.free;
readln;
end.</langsyntaxhighlight>
{{out}}
<pre>sh-4.4# ./Periode
Line 2,286 ⟶ 2,445:
{{trans|Sidef}}
{{libheader|ntheory}}
<langsyntaxhighlight lang="perl">use ntheory qw/divisors powmod is_prime/;
 
sub is_long_prime {
Line 2,302 ⟶ 2,461:
for my $n (500, 1000, 2000, 4000, 8000, 16000, 32000, 64000) {
printf "Number of long primes ≤ $n: %d\n", scalar grep { is_long_prime($_) } 1 .. $n;
}</langsyntaxhighlight>
{{out}}
<pre>Long primes ≤ 500:
Line 2,319 ⟶ 2,478:
 
Faster due to going directly over primes and using znorder. Takes one second to count to 8,192,000.
<langsyntaxhighlight lang="perl">use ntheory qw/forprimes znorder/;
my($t,$z)=(0,0);
forprimes {
Line 2,325 ⟶ 2,484:
$t++ if defined $z && $z+1 == $_;
} 8192000;
print "$t\n";</langsyntaxhighlight>
{{out}}
<pre>206594</pre>
Line 2,331 ⟶ 2,490:
=={{header|Phix}}==
Slow version:
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #008080;">function</span> <span style="color: #000000;">is_long_prime</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">rr</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">period</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
Line 2,346 ⟶ 2,505:
<span style="color: #008080;">return</span> <span style="color: #000000;">period</span><span style="color: #0000FF;">=</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<!--</langsyntaxhighlight>-->
(use the same main() as below but limit maxN to 8 iterations)
 
Much faster version:
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #008080;">function</span> <span style="color: #000000;">is_long_prime</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">f</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">factors</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
Line 2,400 ⟶ 2,559:
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">main</span><span style="color: #0000FF;">()</span>
<!--</langsyntaxhighlight>-->
{{out}}
slow version:
Line 2,439 ⟶ 2,598:
8192000 is 206594 (1 minute and 60s)
</pre>
 
=={{header|Picat}}==
<syntaxhighlight lang="picat">go =>
println(findall(P, (member(P,primes(500)),long_prime(P)))),
nl,
println("Number of long primes up to limit are:"),
foreach(Limit in [500,1_000,2_000,4_000,8_000,16_000,32_000,64_000])
printf(" <= %5d: %4d\n", Limit, count_all( (member(P,primes(Limit)), long_prime(P)) ))
end,
nl.
 
long_prime(P) =>
get_rep_len(P) == (P-1).
 
%
% Get the length of the repeating cycle for 1/n
%
get_rep_len(I) = Len =>
FoundRemainders = {0 : _K in 1..I+1},
Value = 1,
Position = 1,
while (FoundRemainders[Value+1] == 0, Value != 0)
FoundRemainders[Value+1] := Position,
Value := (Value*10) mod I,
Position := Position+1
end,
Len = Position-FoundRemainders[Value+1].</syntaxhighlight>
 
{{out}}
<pre>[7,17,19,23,29,47,59,61,97,109,113,131,149,167,179,181,193,223,229,233,257,263,269,313,337,367,379,383,389,419,433,461,487,491,499]
 
Number of long primes up to limit are:
<= 500: 35
<= 1000: 60
<= 2000: 116
<= 4000: 218
<= 8000: 390
<= 16000: 716
<= 32000: 1300
<= 64000: 2430</pre>
 
=={{header|Prolog}}==
{{works with|SWI Prolog}}
<langsyntaxhighlight lang="prolog">% See https://en.wikipedia.org/wiki/Full_reptend_prime
long_prime(Prime):-
is_prime(Prime),
Line 2,517 ⟶ 2,716:
 
main:-
main(256000).</langsyntaxhighlight>
 
Module for finding prime numbers up to some limit:
<langsyntaxhighlight lang="prolog">:- module(prime_numbers, [find_prime_numbers/1, is_prime/1]).
:- dynamic is_prime/1.
 
Line 2,561 ⟶ 2,760:
cross_out(S, N, P):-
Q is S + 2 * P,
cross_out(Q, N, P).</langsyntaxhighlight>
 
{{out}}
Line 2,580 ⟶ 2,779:
% 8,564,024 inferences, 0.991 CPU in 1.040 seconds (95% CPU, 8641390 Lips)
true.
</pre>
===alternative version===
the smallest divisor d of p - 1 such that 10^d = 1 (mod p)
is the length of the period of the decimal expansion of 1/p
<syntaxhighlight lang="prolog">isPrime(A):-
A1 is ceil(sqrt(A)),
between(2, A1, N),
0 =:= A mod N,!,
false.
isPrime(_).
 
divisors(N, Dlist):-
N1 is floor(sqrt(N)),
numlist(1, N1, Ds0),
include([D]>>(N mod D =:= 0), Ds0, Ds1),
reverse(Ds1, [Dh|Dt]),
( Dh * Dh < N
-> Ds1a = [Dh|Dt]
; Ds1a = Dt
),
maplist([X,Y]>>(Y is N div X), Ds1a, Ds2),
append(Ds1, Ds2, Dlist).
 
longPrime(P):-
divisors(P - 1, Dlist),
longPrime(P, Dlist).
 
longPrime(_,[]):- false.
longPrime(P, [D|Dtail]):-
powm(10, D, P) =\= 1,!,
longPrime(P, Dtail).
longPrime(P, [D|_]):-!,
D =:= P - 1.
 
isLongPrime(N):-
isPrime(N),
longPrime(N).
 
longPrimes(N, LongPrimes):-
numlist(7, N, List),
include(isLongPrime, List, LongPrimes).
 
run([]):-!.
run([Limit|Tail]):-
statistics(runtime,[Start|_]),
longPrimes(Limit, LongPrimes),
length(LongPrimes, Num),
statistics(runtime,[Stop|_]),
Runtime is Stop - Start,
writef('there are%5r long primes up to%6r [time (ms)%5r]\n',[Num, Limit, Runtime]),
run(Tail).
 
do:- longPrimes(500, LongPrimes),
writeln('long primes up to 500:'),
writeln(LongPrimes),
numlist(0, 7, List),
maplist([X, Y]>>(Y is 500 * 2**X), List, LimitList),
run(LimitList).</syntaxhighlight>
{{out}}
<pre>long primes up to 500:
[7,17,19,23,29,47,59,61,97,109,113,131,149,167,179,181,193,223,229,233,257,263,269,313,337,367,379,383,389,419,433,461,487,491,499]
there are 35 long primes up to 500 [time (ms) 7]
there are 60 long primes up to 1000 [time (ms) 16]
there are 116 long primes up to 2000 [time (ms) 42]
there are 218 long primes up to 4000 [time (ms) 98]
there are 390 long primes up to 8000 [time (ms) 242]
there are 716 long primes up to 16000 [time (ms) 603]
there are 1300 long primes up to 32000 [time (ms) 1507]
there are 2430 long primes up to 64000 [time (ms) 3851]
</pre>
 
=={{header|PureBasic}}==
<langsyntaxhighlight PureBasiclang="purebasic">#MAX=64000
If OpenConsole()=0 : End 1 : EndIf
 
Line 2,608 ⟶ 2,876:
If i>n : PrintN(RSet(Str(n),8)+" is "+Str(c)) : n+n : EndIf
Next
Input()</langsyntaxhighlight>
{{out}}
<pre>_______________Long primes upto 500_______________
Line 2,629 ⟶ 2,897:
=={{header|Python}}==
{{trans|Kotlin}}
<langsyntaxhighlight lang="python">def sieve(limit):
primes = []
c = [False] * (limit + 1) # composite = true
Line 2,677 ⟶ 2,945:
print('\nThe number of long primes up to:')
for (i, total) in enumerate(totals):
print(' %5d is %d' % (numbers[i], total))</langsyntaxhighlight>
{{out}}
<pre>
Line 2,700 ⟶ 2,968:
<code>bsearchwith</code> is defined at [[Binary search#Quackery]].
 
<langsyntaxhighlight Quackerylang="quackery"> [ over size 0 swap 2swap
bsearchwith < drop ] is search ( [ --> n )
 
Line 2,730 ⟶ 2,998:
[ dup echo say " --> "
dip dup search echo cr ]
drop</langsyntaxhighlight>
 
{{out}}
Line 2,749 ⟶ 3,017:
{{trans|Go}} (at least '''find-period''')
 
<langsyntaxhighlight lang="racket">#lang racket
(require math/number-theory)
 
Line 2,774 ⟶ 3,042:
(module+ test
(require rackunit)
(check-equal? (map find-period '(7 11 977)) '(6 2 976)))</langsyntaxhighlight>
 
{{out}}
Line 2,791 ⟶ 3,059:
{{works with|Rakudo|2018.06}}
Not very fast as the numbers get larger.
<syntaxhighlight lang="raku" perl6line>use Math::Primesieve;
my $sieve = Math::Primesieve.new;
 
Line 2,819 ⟶ 3,087:
say "\nNumber of long primes ≤ $upto: ", +@long-primes;
$from = $upto;
}</langsyntaxhighlight>
{{out}}
<pre>Long primes ≤ 500:
Line 2,848 ⟶ 3,116:
For every &nbsp; '''doubling''' &nbsp; of the limit, it takes about roughly &nbsp; '''5''' &nbsp; times longer to compute the long primes.
===uses odd numbers===
<langsyntaxhighlight lang="rexx">/*REXX pgm calculates/displays base ten long primes (AKA golden primes, proper primes,*/
/*───────────────────── maximal period primes, long period primes, full reptend primes).*/
parse arg a /*obtain optional argument from the CL.*/
Line 2,869 ⟶ 3,137:
.len: procedure; parse arg x; r=1; do x; r= 10*r // x; end /*x*/
rr=r; do p=1 until r==rr; r= 10*r // x; end /*p*/
return p</langsyntaxhighlight>
{{out|output|text=&nbsp; when using the internal default inputs:}}
<pre>
Line 2,900 ⟶ 3,168:
===uses odd numbers, some prime tests===
This REXX version is about &nbsp; '''2''' &nbsp; times faster than the 1<sup>st</sup> REXX version &nbsp; (because it does some primality testing).
<langsyntaxhighlight lang="rexx">/*REXX pgm calculates/displays base ten long primes (AKA golden primes, proper primes,*/
/*───────────────────── maximal period primes, long period primes, full reptend primes).*/
parse arg a /*obtain optional argument from the CL.*/
Line 2,927 ⟶ 3,195:
.len: procedure; parse arg x; r=1; do x; r= 10*r // x; end /*x*/
rr=r; do p=1 until r==rr; r= 10*r // x; end /*p*/
return p</langsyntaxhighlight>
{{out|output|text=&nbsp; is identical to the 1<sup>st</sup> REXX version.}}
 
===uses primes===
This REXX version is about &nbsp; '''5''' &nbsp; times faster than the 1<sup>st</sup> REXX version &nbsp; (because it only tests primes).
<langsyntaxhighlight lang="rexx">/*REXX pgm calculates/displays base ten long primes (AKA golden primes, proper primes,*/
/*───────────────────── maximal period primes, long period primes, full reptend primes).*/
parse arg a /*obtain optional argument from the CL.*/
Line 2,969 ⟶ 3,237:
.len: procedure; parse arg x; r=1; do x; r= 10*r // x; end /*x*/
rr=r; do p=1 until r==rr; r= 10*r // x; end /*p*/
return p</langsyntaxhighlight>
{{out|output|text=&nbsp; is identical to the 1<sup>st</sup> REXX version.}} <br>
 
=={{header|RPL}}==
{{works with|HP|49}}
« → n
« 0 1
'''DO''' 10 * n MOD SWAP 1 + SWAP
'''UNTIL''' DUP 1 ≤ '''END'''
DROP
» » '<span style="color:blue">PERIOD</span>' STO <span style="color:grey">@ ''( n → length of 1/n period )''</span>
« { } 7
'''WHILE''' DUP 500 < '''REPEAT'''
'''IF''' DUP <span style="color:blue">PERIOD</span> OVER 1 - == '''THEN''' SWAP OVER + SWAP '''END'''
NEXTPRIME
'''END'''
DROP
» '<span style="color:blue">TASK1</span>' STO
« { 500 1000 2000 4000 8000 16000 32000 } → t
« t NOT 7
'''WHILE''' DUP 1000 < '''REPEAT'''
'''IF''' DUP <span style="color:blue">PERIOD</span> OVER 1 - == '''THEN''' t OVER ≥ ROT ADD SWAP '''END'''
NEXTPRIME
'''END'''
DROP t SWAP
2 « "<" ROT + →TAG » DOLIST
» » '<span style="color:blue">TASK2</span>' STO
{{out}}
<pre>
2: {7 17 19 23 29 47 59 61 97 109 113 131 149 167 179 181 193 223 229 233 257 263 269 313 337 367 379 383 389 419 433 461 487 491 499}
1: {<500:35 <1000:60 <2000:116 <4000:218 <8000:390 <16000:716 <32000:1300}
</pre>
 
=={{header|Ruby}}==
Line 2,976 ⟶ 3,276:
Run as: $ ruby longprimes.rb
Finding long prime numbers using finding period location (translation of Python's module def findPeriod(n))
<langsyntaxhighlight Rubylang="ruby">require 'prime'
 
batas = 64_000 # limit number
Line 3,007 ⟶ 3,307:
end
 
puts "\n\nTime: #{Time.now - start}"</langsyntaxhighlight>
 
{{out}}
Line 3,025 ⟶ 3,325:
 
Alternatively, by using primitive way: converting value into string and make assessment for proper repetend position. Indeed produce same information, but with longer time.
<langsyntaxhighlight Rubylang="ruby">require 'prime'
require 'bigdecimal'
require 'strscan'
Line 3,062 ⟶ 3,362:
end
 
puts "\n\nTime: #{Time.now - start}"</langsyntaxhighlight>
 
{{out}}
Line 3,072 ⟶ 3,372:
{{trans|Crystal of Sidef}}
Fastest version.
<langsyntaxhighlight lang="ruby">def prime?(n) # P3 Prime Generator primality test
return n | 1 == 3 if n < 5 # n: 2,3|true; 0,1,4|false
return false if n.gcd(6) != 1 # this filters out 2/3 of all integers
Line 3,104 ⟶ 3,404:
puts "Number of long primes ≤ #{n}: #{(7..n).count { |pc| long_prime? pc }}"
end
puts "\nTime: #{(Time.now - start)} secs"</langsyntaxhighlight>
 
{{out}}
Line 3,123 ⟶ 3,423:
 
=={{header|Rust}}==
<langsyntaxhighlight lang="rust">// main.rs
// References:
// https://en.wikipedia.org/wiki/Full_reptend_prime
Line 3,199 ⟶ 3,499:
fn main() {
long_primes(500, 8192000);
}</langsyntaxhighlight>
 
<langsyntaxhighlight lang="rust">// prime_sieve.rs
use crate::bit_array;
 
Line 3,236 ⟶ 3,536:
!self.composite.get(n / 2 - 1)
}
}</langsyntaxhighlight>
 
<langsyntaxhighlight lang="rust">// bit_array.rs
pub struct BitArray {
array: Vec<u32>,
Line 3,261 ⟶ 3,561:
}
}
}</langsyntaxhighlight>
 
{{out}}
Line 3,284 ⟶ 3,584:
</pre>
===Rust FP===
<langsyntaxhighlight lang="rust">fn is_oddprime(n: u64) -> bool {
let limit = (n as f64).sqrt().ceil() as u64;
(3..=limit).step_by(2).all(|a| n % a > 0)
Line 3,306 ⟶ 3,606:
else {res}
}
iter(base, &modulo, exp -, 1,base % modulo)
}
 
Line 3,340 ⟶ 3,640:
count, limit, duration);
}
}</langsyntaxhighlight>
{{out}}
<pre>
long primes up to 500:
[7, 17, 19, 23, 29, 47, 59, 61, 97, 109, 113, 131, 149, 167, 179, 181, 193, 223, 229, 233, 257, 263, 269, 313, 337, 367, 379, 383, 389, 419, 433, 461, 487, 491, 499]
 
there are 35 long primes up to 500 [time(ms) 0]
there are 60 long primes up to 1000 [time(ms) 1]
there are 116 long primes up to 2000 [time(ms) 2]
there are 218 long primes up to 4000 [time(ms) 5]
there are 390 long primes up to 8000 [time(ms) 13]
there are 716 long primes up to 16000 [time(ms) 31]
there are 1300 long primes up to 32000 [time(ms) 36]
there are 2430 long primes up to 64000 [time(ms) 41]
</pre>
 
=={{header|Scala}}==
<langsyntaxhighlight lang="scala">object LongPrimes extends App {
def primeStream = LazyList.from(3, 2)
.filter(p => (3 to math.sqrt(p).ceil.toInt by 2).forall(p % _ > 0))
Line 3,368 ⟶ 3,682:
println(f"there are $count%4d long primes up to $limit%5d")
}
}</langsyntaxhighlight>
{{out}}
<pre>
Line 3,386 ⟶ 3,700:
=={{header|Sidef}}==
The smallest divisor d of p-1 such that 10^d = 1 (mod p), is the length of the period of the decimal expansion of 1/p.
<langsyntaxhighlight lang="ruby">func is_long_prime(p) {
 
for d in (divisors(p-1)) {
Line 3,402 ⟶ 3,716:
for n in ([500, 1000, 2000, 4000, 8000, 16000, 32000, 64000]) {
say ("Number of long primes ≤ #{n}: ", primes(n).count_by(is_long_prime))
}</langsyntaxhighlight>
{{out}}
<pre>
Line 3,419 ⟶ 3,733:
Alternatively, we can implement the ''is_long_prime(p)'' function using the `znorder(a, p)` built-in method, which is considerably faster:
 
<langsyntaxhighlight lang="ruby">func is_long_prime(p) {
znorder(10, p) == p-1
}</langsyntaxhighlight>
 
=={{header|Swift}}==
 
<langsyntaxhighlight lang="swift">public struct Eratosthenes: Sequence, IteratorProtocol {
private let n: Int
private let limit: Int
Line 3,489 ⟶ 3,803:
for key in counts.keys.sorted() {
print("There are \(counts[key]!) long primes less than \(key)")
}</langsyntaxhighlight>
 
{{out}}
Line 3,505 ⟶ 3,819:
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<langsyntaxhighlight lang="vbnet">Imports System, System.Collections.Generic, System.Linq, System.Console
 
Module LongPrimes
Line 3,544 ⟶ 3,858:
End Function
 
End Module</langsyntaxhighlight>
{{out}}
Same output as C#.
Line 3,552 ⟶ 3,866:
{{libheader|Wren-fmt}}
{{libheader|Wren-math}}
<langsyntaxhighlight ecmascriptlang="wren">import "./fmt" for Fmt
import "./math" for Int
// finds the period of the reciprocal of n
Line 3,593 ⟶ 3,907:
var i = 0
for (total in totals) {
SystemFmt.print(" %(Fmt.$5d is $d(5", numbers[i])), is %(total)")
i = i + 1
}</langsyntaxhighlight>
 
{{out}}
Line 3,616 ⟶ 3,930:
{{trans|C}}
{{works with|Windows XBasic}}
<langsyntaxhighlight lang="xbasic">
PROGRAM "longprimes"
VERSION "0.0002"
Line 3,717 ⟶ 4,031:
 
END PROGRAM
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 3,739 ⟶ 4,053:
Using GMP (GNU Multiple Precision Arithmetic Library, probabilistic
primes), because it is easy and fast to generate primes.
<langsyntaxhighlight lang="zkl">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
Line 3,755 ⟶ 4,069:
}
period
}</langsyntaxhighlight>
 
<langsyntaxhighlight lang="zkl">fiveHundred:=longPrimes.filter('<(500));
println("The long primes up to 500 are:\n",longPrimes.filter('<(500)).concat(","));
 
Line 3,763 ⟶ 4,077:
foreach n in (T(500, 1000, 2000, 4000, 8000, 16000, 32000, 64000)){
println(" %5d is %d".fmt( n, longPrimes.filter1n('>(n)) ));
}</langsyntaxhighlight>
{{out}}
<pre>
Tigerofdarkness
3,026

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/283962...353586"