Long primes: Difference between revisions
Added Algol 68
(Added Algol 68) |
|||
(14 intermediate revisions by 7 users not shown) | |||
Line 55:
{{trans|Python}}
<
[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))</
{{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.
<
script o
property numberList : {missing value}
Line 234 ⟶ 304:
end longPrimesTask
longPrimesTask()</
{{output}}
Line 250 ⟶ 320:
=={{header|C}}==
{{trans|Go}}
<
#include <stdlib.h>
Line 330 ⟶ 400:
free(primes);
return 0;
}</
{{out}}
Line 350 ⟶ 420:
=={{header|C sharp}}==
{{works with|C sharp|7}}
<
using System.Collections.Generic;
using System.Linq;
Line 392 ⟶ 462:
for (; j<= lim; j++) if (!flags[j]) yield return j;
}
}</
{{out}}
<pre>
Line 407 ⟶ 477:
=={{header|C++}}==
{{trans|C}}
<
#include <iomanip>
#include <iostream>
Line 494 ⟶ 564:
delete [] totals;
}
</syntaxhighlight>
{{out}}
<pre>
Line 515 ⟶ 585:
=={{header|Common Lisp}}==
{{trans|Raku}}
<
(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>
{{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.
<
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"</
{{out}}
Line 598 ⟶ 668:
Faster: using divisors of (p - 1) and powmod().
<
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"</
{{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]]
<
// 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>
===The Task===
<
primes |> Seq.skip 3 |> Seq.takeWhile(fun n->n<500) |> Seq.filter isLongPrime |> Seq.iter(printf "%d ")
</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
</pre>
<
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>
{{out}}
<pre>
There are 35 long primes less than 500
</pre>
<
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>
{{out}}
<pre>
There are 60 long primes less than 1000
</pre>
<
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>
{{out}}
<pre>
There are 116 long primes less than 2000
</pre>
<
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>
{{out}}
<pre>
There are 218 long primes less than 4000
</pre>
<
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>
{{out}}
<pre>
There are 390 long primes less than 8000
</pre>
<
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>
{{out}}
<pre>
There are 716 long primes less than 16000
</pre>
<
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>
{{out}}
<pre>
There are 1300 long primes less than 32000
</pre>
<
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>
{{out}}
<pre>
There are 2430 long primes less than 64000
</pre>
<
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>
{{out}}
<pre>
Line 748 ⟶ 877:
Real: 00:00:01.294, CPU: 00:00:01.300, GC gen0: 27, gen1: 0
</pre>
<
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>
{{out}}
<pre>
Line 756 ⟶ 885:
Real: 00:00:03.434, CPU: 00:00:03.440, GC gen0: 58, gen1: 0
</pre>
<
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>
{{out}}
<pre>
Line 764 ⟶ 893:
Real: 00:00:09.248, CPU: 00:00:09.260, GC gen0: 128, gen1: 0
</pre>
<
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>
{{out}}
<pre>
Line 774 ⟶ 903:
=={{header|Factor}}==
<
math.primes.factors memoize prettyprint sequences ;
IN: rosetta-code.long-primes
Line 796 ⟶ 925:
[ .#lp<=n ] each ;
MAIN: long-primes-demo</
{{out}}
<pre>
Line 815 ⟶ 944:
{{works with|Gforth}}
The prime sieve code was borrowed from [[Sieve of Eratosthenes#Forth]].
<
: notprime! ( n -- ) here + 1 swap c! ;
Line 904 ⟶ 1,033:
main
bye</
{{out}}
Line 925 ⟶ 1,054:
=={{header|FreeBASIC}}==
<
' compile with: fbc -s console
Line 999 ⟶ 1,128:
Print : Print "hit any key to end program"
Sleep
End</
{{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}}==
<
import "fmt"
Line 1,082 ⟶ 1,211:
fmt.Printf(" %5d is %d\n", numbers[i], total)
}
}</
{{out}}
Line 1,100 ⟶ 1,229:
</pre>
=={{header|Haskell}}==
<
longPrimesUpTo :: Int -> [Int]
Line 1,137 ⟶ 1,266:
)
putStrLn ("500 is " <> show (length fiveHundred))
display 1000</
{{out}}
<pre>The long primes up to 35 are:
Line 1,199 ⟶ 1,328:
=={{header|Java}}==
{{trans|C}}
<
import java.util.LinkedList;
import java.util.List;
Line 1,269 ⟶ 1,398:
}
}
</syntaxhighlight>
{{out}}
<pre>
Line 1,297 ⟶ 1,426:
'''Preliminaries'''
<syntaxhighlight lang="jq">
def count(s): reduce s as $x (0; .+1);
Line 1,329 ⟶ 1,458:
2, 3, ([2,3] | next);
</syntaxhighlight>
'''Long Primes'''
<syntaxhighlight 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>
{{out}}
<pre>
Line 1,417 ⟶ 1,546:
=={{header|Julia}}==
{{trans|Sidef}}
<
using Primes
Line 1,448 ⟶ 1,577:
println("Number of long primes ≤ $i: $(sum(map(x->islongprime(x), 1:i)))")
end
</syntaxhighlight>
{{output}}<pre>
Long primes ≤ 500:
Line 1,466 ⟶ 1,595:
=={{header|Kotlin}}==
{{trans|Go}}
<
fun sieve(limit: Int): List<Int> {
Line 1,526 ⟶ 1,655:
System.out.printf(" %5d is %d\n", numbers[i], total)
}
}</
{{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">
Module LongPrimes {
Sieve=lambda (limit)->{
Line 1,618 ⟶ 1,747:
}
LongPrimes
</syntaxhighlight>
{{out}}
Line 1,637 ⟶ 1,766:
=={{header|Maple}}==
<syntaxhighlight lang="maple">
with(NumberTheory):
with(ArrayTools):
Line 1,672 ⟶ 1,801:
numOfLongPrimes;
</syntaxhighlight>
{{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}}==
<
lPrimes[500]
Length /@ lPrimes /@ ( 250*2^Range[8])</
{{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">
;;; 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>
{{out}}
<pre>
Line 1,740 ⟶ 1,899:
=={{header|Nim}}==
{{trans|Kotlin}}
<
Line 1,795 ⟶ 1,954:
echo "\nThe number of long primes up to:"
for i, total in totals:
echo &" {Numbers[i]:>5} is {total}"</
{{out}}
Line 1,815 ⟶ 1,974:
www . arndt-bruenner.de/mathe/scripts/periodenlaenge.htm
<
program Periode;
Line 2,258 ⟶ 2,417:
F.free;
readln;
end.</
{{out}}
<pre>sh-4.4# ./Periode
Line 2,286 ⟶ 2,445:
{{trans|Sidef}}
{{libheader|ntheory}}
<
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;
}</
{{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.
<
my($t,$z)=(0,0);
forprimes {
Line 2,325 ⟶ 2,484:
$t++ if defined $z && $z+1 == $_;
} 8192000;
print "$t\n";</
{{out}}
<pre>206594</pre>
Line 2,331 ⟶ 2,490:
=={{header|Phix}}==
Slow version:
<!--<
<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>
<!--</
(use the same main() as below but limit maxN to 8 iterations)
Much faster version:
<!--<
<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>
<!--</
{{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}}
<
long_prime(Prime):-
is_prime(Prime),
Line 2,517 ⟶ 2,716:
main:-
main(256000).</
Module for finding prime numbers up to some limit:
<
:- dynamic is_prime/1.
Line 2,561 ⟶ 2,760:
cross_out(S, N, P):-
Q is S + 2 * P,
cross_out(Q, N, P).</
{{out}}
Line 2,582 ⟶ 2,781:
</pre>
===alternative version===
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),
Line 2,636 ⟶ 2,836:
numlist(0, 7, List),
maplist([X, Y]>>(Y is 500 * 2**X), List, LimitList),
run(LimitList).</
{{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}}==
<
If OpenConsole()=0 : End 1 : EndIf
Line 2,664 ⟶ 2,876:
If i>n : PrintN(RSet(Str(n),8)+" is "+Str(c)) : n+n : EndIf
Next
Input()</
{{out}}
<pre>_______________Long primes upto 500_______________
Line 2,685 ⟶ 2,897:
=={{header|Python}}==
{{trans|Kotlin}}
<
primes = []
c = [False] * (limit + 1) # composite = true
Line 2,733 ⟶ 2,945:
print('\nThe number of long primes up to:')
for (i, total) in enumerate(totals):
print(' %5d is %d' % (numbers[i], total))</
{{out}}
<pre>
Line 2,756 ⟶ 2,968:
<code>bsearchwith</code> is defined at [[Binary search#Quackery]].
<
bsearchwith < drop ] is search ( [ --> n )
Line 2,786 ⟶ 2,998:
[ dup echo say " --> "
dip dup search echo cr ]
drop</
{{out}}
Line 2,805 ⟶ 3,017:
{{trans|Go}} (at least '''find-period''')
<
(require math/number-theory)
Line 2,830 ⟶ 3,042:
(module+ test
(require rackunit)
(check-equal? (map find-period '(7 11 977)) '(6 2 976)))</
{{out}}
Line 2,847 ⟶ 3,059:
{{works with|Rakudo|2018.06}}
Not very fast as the numbers get larger.
<syntaxhighlight lang="raku"
my $sieve = Math::Primesieve.new;
Line 2,875 ⟶ 3,087:
say "\nNumber of long primes ≤ $upto: ", +@long-primes;
$from = $upto;
}</
{{out}}
<pre>Long primes ≤ 500:
Line 2,904 ⟶ 3,116:
For every '''doubling''' of the limit, it takes about roughly '''5''' times longer to compute the long primes.
===uses odd numbers===
<
/*───────────────────── maximal period primes, long period primes, full reptend primes).*/
parse arg a /*obtain optional argument from the CL.*/
Line 2,925 ⟶ 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</
{{out|output|text= when using the internal default inputs:}}
<pre>
Line 2,956 ⟶ 3,168:
===uses odd numbers, some prime tests===
This REXX version is about '''2''' times faster than the 1<sup>st</sup> REXX version (because it does some primality testing).
<
/*───────────────────── maximal period primes, long period primes, full reptend primes).*/
parse arg a /*obtain optional argument from the CL.*/
Line 2,983 ⟶ 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</
{{out|output|text= is identical to the 1<sup>st</sup> REXX version.}}
===uses primes===
This REXX version is about '''5''' times faster than the 1<sup>st</sup> REXX version (because it only tests primes).
<
/*───────────────────── maximal period primes, long period primes, full reptend primes).*/
parse arg a /*obtain optional argument from the CL.*/
Line 3,025 ⟶ 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</
{{out|output|text= 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 3,032 ⟶ 3,276:
Run as: $ ruby longprimes.rb
Finding long prime numbers using finding period location (translation of Python's module def findPeriod(n))
<
batas = 64_000 # limit number
Line 3,063 ⟶ 3,307:
end
puts "\n\nTime: #{Time.now - start}"</
{{out}}
Line 3,081 ⟶ 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.
<
require 'bigdecimal'
require 'strscan'
Line 3,118 ⟶ 3,362:
end
puts "\n\nTime: #{Time.now - start}"</
{{out}}
Line 3,128 ⟶ 3,372:
{{trans|Crystal of Sidef}}
Fastest version.
<
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,160 ⟶ 3,404:
puts "Number of long primes ≤ #{n}: #{(7..n).count { |pc| long_prime? pc }}"
end
puts "\nTime: #{(Time.now - start)} secs"</
{{out}}
Line 3,179 ⟶ 3,423:
=={{header|Rust}}==
<
// References:
// https://en.wikipedia.org/wiki/Full_reptend_prime
Line 3,255 ⟶ 3,499:
fn main() {
long_primes(500, 8192000);
}</
<
use crate::bit_array;
Line 3,292 ⟶ 3,536:
!self.composite.get(n / 2 - 1)
}
}</
<
pub struct BitArray {
array: Vec<u32>,
Line 3,317 ⟶ 3,561:
}
}
}</
{{out}}
Line 3,340 ⟶ 3,584:
</pre>
===Rust FP===
<
let limit = (n as f64).sqrt().ceil() as u64;
(3..=limit).step_by(2).all(|a| n % a > 0)
Line 3,362 ⟶ 3,606:
else {res}
}
iter(base, &modulo, exp
}
Line 3,396 ⟶ 3,640:
count, limit, duration);
}
}</
{{out}}
<pre>
Line 3,413 ⟶ 3,657:
=={{header|Scala}}==
<
def primeStream = LazyList.from(3, 2)
.filter(p => (3 to math.sqrt(p).ceil.toInt by 2).forall(p % _ > 0))
Line 3,438 ⟶ 3,682:
println(f"there are $count%4d long primes up to $limit%5d")
}
}</
{{out}}
<pre>
Line 3,456 ⟶ 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.
<
for d in (divisors(p-1)) {
Line 3,472 ⟶ 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))
}</
{{out}}
<pre>
Line 3,489 ⟶ 3,733:
Alternatively, we can implement the ''is_long_prime(p)'' function using the `znorder(a, p)` built-in method, which is considerably faster:
<
znorder(10, p) == p-1
}</
=={{header|Swift}}==
<
private let n: Int
private let limit: Int
Line 3,559 ⟶ 3,803:
for key in counts.keys.sorted() {
print("There are \(counts[key]!) long primes less than \(key)")
}</
{{out}}
Line 3,575 ⟶ 3,819:
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<
Module LongPrimes
Line 3,614 ⟶ 3,858:
End Function
End Module</
{{out}}
Same output as C#.
Line 3,622 ⟶ 3,866:
{{libheader|Wren-fmt}}
{{libheader|Wren-math}}
<
import "./math" for Int
// finds the period of the reciprocal of n
Line 3,663 ⟶ 3,907:
var i = 0
for (total in totals) {
i = i + 1
}</
{{out}}
Line 3,686 ⟶ 3,930:
{{trans|C}}
{{works with|Windows XBasic}}
<
PROGRAM "longprimes"
VERSION "0.0002"
Line 3,787 ⟶ 4,031:
END PROGRAM
</syntaxhighlight>
{{out}}
<pre>
Line 3,809 ⟶ 4,053:
Using GMP (GNU Multiple Precision Arithmetic Library, probabilistic
primes), because it is easy and fast to generate primes.
<
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,825 ⟶ 4,069:
}
period
}</
<
println("The long primes up to 500 are:\n",longPrimes.filter('<(500)).concat(","));
Line 3,833 ⟶ 4,077:
foreach n in (T(500, 1000, 2000, 4000, 8000, 16000, 32000, 64000)){
println(" %5d is %d".fmt( n, longPrimes.filter1n('>(n)) ));
}</
{{out}}
<pre>
|