Long primes: Difference between revisions
m
syntax highlighting fixup automation
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
|||
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 128:
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:
end longPrimesTask
longPrimesTask()</
{{output}}
Line 250:
=={{header|C}}==
{{trans|Go}}
<
#include <stdlib.h>
Line 330:
free(primes);
return 0;
}</
{{out}}
Line 350:
=={{header|C sharp}}==
{{works with|C sharp|7}}
<
using System.Collections.Generic;
using System.Linq;
Line 392:
for (; j<= lim; j++) if (!flags[j]) yield return j;
}
}</
{{out}}
<pre>
Line 407:
=={{header|C++}}==
{{trans|C}}
<
#include <iomanip>
#include <iostream>
Line 494:
delete [] totals;
}
</syntaxhighlight>
{{out}}
<pre>
Line 515:
=={{header|Common Lisp}}==
{{trans|Raku}}
<
(defun primep (n)
(cond ((and (<= n 3) (> n 1)) t)
Line 541:
(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:
{{trans|Sidef}}
Simpler but slower.
<
def prime?(n) # P3 Prime Generator primality test
Line 578:
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:
Faster: using divisors of (p - 1) and powmod().
<
def prime?(n) # P3 Prime Generator primality test
Line 643:
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 668:
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:
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:
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:
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:
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:
=={{header|Factor}}==
<
math.primes.factors memoize prettyprint sequences ;
IN: rosetta-code.long-primes
Line 796:
[ .#lp<=n ] each ;
MAIN: long-primes-demo</
{{out}}
<pre>
Line 815:
{{works with|Gforth}}
The prime sieve code was borrowed from [[Sieve of Eratosthenes#Forth]].
<
: notprime! ( n -- ) here + 1 swap c! ;
Line 904:
main
bye</
{{out}}
Line 925:
=={{header|FreeBASIC}}==
<
' compile with: fbc -s console
Line 999:
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:
=={{header|Go}}==
<
import "fmt"
Line 1,082:
fmt.Printf(" %5d is %d\n", numbers[i], total)
}
}</
{{out}}
Line 1,100:
</pre>
=={{header|Haskell}}==
<
longPrimesUpTo :: Int -> [Int]
Line 1,137:
)
putStrLn ("500 is " <> show (length fiveHundred))
display 1000</
{{out}}
<pre>The long primes up to 35 are:
Line 1,199:
=={{header|Java}}==
{{trans|C}}
<
import java.util.LinkedList;
import java.util.List;
Line 1,269:
}
}
</syntaxhighlight>
{{out}}
<pre>
Line 1,297:
'''Preliminaries'''
<syntaxhighlight lang="jq">
def count(s): reduce s as $x (0; .+1);
Line 1,329:
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:
| "Number of long primes ≤ \(.): \(count_long_primes)" )
</syntaxhighlight>
{{out}}
<pre>
Line 1,417:
=={{header|Julia}}==
{{trans|Sidef}}
<
using Primes
Line 1,448:
println("Number of long primes ≤ $i: $(sum(map(x->islongprime(x), 1:i)))")
end
</syntaxhighlight>
{{output}}<pre>
Long primes ≤ 500:
Line 1,466:
=={{header|Kotlin}}==
{{trans|Go}}
<
fun sieve(limit: Int): List<Int> {
Line 1,526:
System.out.printf(" %5d is %d\n", numbers[i], total)
}
}</
{{output}}
Line 1,548:
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:
}
LongPrimes
</syntaxhighlight>
{{out}}
Line 1,637:
=={{header|Maple}}==
<syntaxhighlight lang="maple">
with(NumberTheory):
with(ArrayTools):
Line 1,672:
numOfLongPrimes;
</syntaxhighlight>
{{out}}<pre>
[7, 17, 19, 23, 29, 47, 59, 61, 97, 109, 113, 131, 149, 167, 179, 181, 193,
Line 1,684:
=={{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,696:
=={{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:
(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:
=={{header|Nim}}==
{{trans|Kotlin}}
<
Line 1,795:
echo "\nThe number of long primes up to:"
for i, total in totals:
echo &" {Numbers[i]:>5} is {total}"</
{{out}}
Line 1,815:
www . arndt-bruenner.de/mathe/scripts/periodenlaenge.htm
<
program Periode;
Line 2,258:
F.free;
readln;
end.</
{{out}}
<pre>sh-4.4# ./Periode
Line 2,286:
{{trans|Sidef}}
{{libheader|ntheory}}
<
sub is_long_prime {
Line 2,302:
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:
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:
$t++ if defined $z && $z+1 == $_;
} 8192000;
print "$t\n";</
{{out}}
<pre>206594</pre>
Line 2,331:
=={{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:
<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:
<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,441:
=={{header|Picat}}==
<
println(findall(P, (member(P,primes(500)),long_prime(P)))),
nl,
Line 2,465:
Position := Position+1
end,
Len = Position-FoundRemainders[Value+1].</
{{out}}
Line 2,482:
=={{header|Prolog}}==
{{works with|SWI Prolog}}
<
long_prime(Prime):-
is_prime(Prime),
Line 2,557:
main:-
main(256000).</
Module for finding prime numbers up to some limit:
<
:- dynamic is_prime/1.
Line 2,601:
cross_out(S, N, P):-
Q is S + 2 * P,
cross_out(Q, N, P).</
{{out}}
Line 2,624:
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
<
A1 is ceil(sqrt(A)),
between(2, A1, N),
Line 2,677:
numlist(0, 7, List),
maplist([X, Y]>>(Y is 500 * 2**X), List, LimitList),
run(LimitList).</
{{out}}
<pre>long primes up to 500:
Line 2,692:
=={{header|PureBasic}}==
<
If OpenConsole()=0 : End 1 : EndIf
Line 2,717:
If i>n : PrintN(RSet(Str(n),8)+" is "+Str(c)) : n+n : EndIf
Next
Input()</
{{out}}
<pre>_______________Long primes upto 500_______________
Line 2,738:
=={{header|Python}}==
{{trans|Kotlin}}
<
primes = []
c = [False] * (limit + 1) # composite = true
Line 2,786:
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,809:
<code>bsearchwith</code> is defined at [[Binary search#Quackery]].
<
bsearchwith < drop ] is search ( [ --> n )
Line 2,839:
[ dup echo say " --> "
dip dup search echo cr ]
drop</
{{out}}
Line 2,858:
{{trans|Go}} (at least '''find-period''')
<
(require math/number-theory)
Line 2,883:
(module+ test
(require rackunit)
(check-equal? (map find-period '(7 11 977)) '(6 2 976)))</
{{out}}
Line 2,900:
{{works with|Rakudo|2018.06}}
Not very fast as the numbers get larger.
<syntaxhighlight lang="raku"
my $sieve = Math::Primesieve.new;
Line 2,928:
say "\nNumber of long primes ≤ $upto: ", +@long-primes;
$from = $upto;
}</
{{out}}
<pre>Long primes ≤ 500:
Line 2,957:
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,978:
.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 3,009:
===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 3,036:
.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,078:
.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>
Line 3,085:
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,116:
end
puts "\n\nTime: #{Time.now - start}"</
{{out}}
Line 3,134:
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,171:
end
puts "\n\nTime: #{Time.now - start}"</
{{out}}
Line 3,181:
{{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,213:
puts "Number of long primes ≤ #{n}: #{(7..n).count { |pc| long_prime? pc }}"
end
puts "\nTime: #{(Time.now - start)} secs"</
{{out}}
Line 3,232:
=={{header|Rust}}==
<
// References:
// https://en.wikipedia.org/wiki/Full_reptend_prime
Line 3,308:
fn main() {
long_primes(500, 8192000);
}</
<
use crate::bit_array;
Line 3,345:
!self.composite.get(n / 2 - 1)
}
}</
<
pub struct BitArray {
array: Vec<u32>,
Line 3,370:
}
}
}</
{{out}}
Line 3,393:
</pre>
===Rust FP===
<
let limit = (n as f64).sqrt().ceil() as u64;
(3..=limit).step_by(2).all(|a| n % a > 0)
Line 3,449:
count, limit, duration);
}
}</
{{out}}
<pre>
Line 3,466:
=={{header|Scala}}==
<
def primeStream = LazyList.from(3, 2)
.filter(p => (3 to math.sqrt(p).ceil.toInt by 2).forall(p % _ > 0))
Line 3,491:
println(f"there are $count%4d long primes up to $limit%5d")
}
}</
{{out}}
<pre>
Line 3,509:
=={{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,525:
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,542:
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,612:
for key in counts.keys.sorted() {
print("There are \(counts[key]!) long primes less than \(key)")
}</
{{out}}
Line 3,628:
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<
Module LongPrimes
Line 3,667:
End Function
End Module</
{{out}}
Same output as C#.
Line 3,675:
{{libheader|Wren-fmt}}
{{libheader|Wren-math}}
<
import "/math" for Int
Line 3,718:
System.print(" %(Fmt.d(5, numbers[i])) is %(total)")
i = i + 1
}</
{{out}}
Line 3,739:
{{trans|C}}
{{works with|Windows XBasic}}
<
PROGRAM "longprimes"
VERSION "0.0002"
Line 3,840:
END PROGRAM
</syntaxhighlight>
{{out}}
<pre>
Line 3,862:
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,878:
}
period
}</
<
println("The long primes up to 500 are:\n",longPrimes.filter('<(500)).concat(","));
Line 3,886:
foreach n in (T(500, 1000, 2000, 4000, 8000, 16000, 32000, 64000)){
println(" %5d is %d".fmt( n, longPrimes.filter1n('>(n)) ));
}</
{{out}}
<pre>
|