Long primes: Difference between revisions

 

 

 

 

:::*   proper primes

 

 

 

:*   [[oeis:A001913|OEIS: A001913]]

<br><br>

 

=={{header|C}}==

{{trans|Go}}

#include <stdlib.h>

free(primes);

return 0;

 

{{out}}

=={{header|C sharp}}==

{{works with|C sharp|7}}

using System.Collections.Generic;

using System.Linq;

for (; j<= lim; j++) if (!flags[j]) yield return j;

}

{{out}}

<pre>

=={{header|C++}}==

{{trans|C}}

#include <iomanip>

#include <iostream>

delete [] totals;

}

{{out}}

<pre>

64000 is 2430

</pre>

 

=={{header|Crystal}}==

{{trans|Sidef}}

Simpler but slower.

 

def prime?(n) # P3 Prime Generator primality test

puts "Number of long primes ≤ #{n}: #{(7..n).count { |pc| long_prime? pc }}"

end

 

{{out}}

 

Faster: using divisors of (p - 1) and powmod().

 

def prime?(n) # P3 Prime Generator primality test

puts "Number of long primes ≤ #{n}: #{(7..n).count { |pc| long_prime? pc }}"

end

{{out}}

<pre>

Run as: $ crystal run longprimes.cr --release

Time: 0.28927228 secs

 

=={{header|F_Sharp|F#}}==

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

fN 1UL 10UL (uint64 g) (uint64 n)

let isLongPrime n=Seq.length (factors (n-1) |> Seq.filter(fun g->(fN n g)=1UL))=1

===The Task===

primes |> Seq.skip 3 |> Seq.takeWhile(fun n->n<500) |> Seq.filter isLongPrime |> Seq.iter(printf "%d ")

{{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)

{{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)

{{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)

{{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)

{{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)

{{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)

{{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)

{{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)

{{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)

{{out}}

<pre>

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)

{{out}}

<pre>

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)

{{out}}

<pre>

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)

{{out}}

<pre>

 

=={{header|Factor}}==

math.primes.factors memoize prettyprint sequences ;

IN: rosetta-code.long-primes

[ .#lp<=n ] each ;

 

{{out}}

<pre>

1300 long primes <= 32000

2430 long primes <= 64000

</pre>

 

=={{header|FreeBASIC}}==

' compile with: fbc -s console

 

Print : Print "hit any key to end program"

Sleep

{{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

 

=={{header|Go}}==

import "fmt"

fmt.Printf(" %5d is %d\n", numbers[i], total)

}

 

{{out}}

</pre>

=={{header|Haskell}}==

 

longPrimesUpTo :: Int -> [Int]

 

display :: Int -> IO ()

 

main :: IO ()

let fiveHundred = longPrimesUpTo 500

{{out}}

[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]

 

16000 is 716

32000 is 1300

 

=={{header|J}}==

=={{header|Java}}==

{{trans|C}}

import java.util.LinkedList;

import java.util.List;

}

}

{{out}}

<pre>

32000 is 1300

64000 is 2430

</pre>

 

=={{header|Julia}}==

{{trans|Sidef}}

using Primes

 

println("Number of long primes ≤ $i: $(sum(map(x->islongprime(x), 1:i)))")

end

{{output}}<pre>

Long primes ≤ 500:

=={{header|Kotlin}}==

{{trans|Go}}

fun sieve(limit: Int): List<Int> {

System.out.printf(" %5d is %d\n", numbers[i], total)

}

 

{{output}}

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.

 

Module LongPrimes {

Sieve=lambda (limit)->{

}

LongPrimes

 

{{out}}

 

=={{header|Maple}}==

with(NumberTheory):

with(ArrayTools):

numOfLongPrimes;

 

{{out}}<pre>

[7, 17, 19, 23, 29, 47, 59, 61, 97, 109, 113, 131, 149, 167, 179, 181, 193,

</pre>

 

lPrimes[500]

{{out}}

<pre>{7, 17, 19, 23, 29, 47, 59, 61, 97, 109, 113, 131, 149, 167, 179,

 

{35, 60, 116, 218, 390, 716, 1300, 2430}

</pre>

 

=={{header|NewLISP}}==

;;; Using the fact that 10 has to be a primitive root mod p

;;; for p to be a reptend/long prime.

(println (find-reptends 500))

(println (map (fn(n) (println n " --> " (length (find-reptends n)))) '(500 1000 2000 4000 8000 16000 32000 64000)))

{{out}}

<pre>

64000 --> 2430

</pre>

 

=={{header|Pascal}}==

www . arndt-bruenner.de/mathe/scripts/periodenlaenge.htm

 

 

{$IFDEF FPC}

{$MODE Delphi}

{$OPTIMIZATION ON}

{$OPTIMIZATION Regvar}

{$else}

{$Apptype Console}

 

sysutils;

const

cBASIS = 10;

{Das sind alle Primzahlen bis 2^16}

{Das reicht fuer al8le Primzahlen bis 2^32}

type

// tFaktorFeld = array [1..15] of TFaktorPotenz;//QWord

 

constructor tFaktorisieren.create;

inherited;

PrimFeldAufbauen;

fFakBasis := cBASIS;

Faktorisierung(fFakBasis);

 

fEulerPhi := 1;

fFakAnzahl := 0;

fAnzahlMoeglicherTeiler := 0;

end;

 

{Testet auf PrimZahl}

var

if fFakZahl = inZahl then

result := (fAnzahlMoeglicherTeiler = 2);

exit;

begin

begin

result := false;

break;

end;

end;

 

{Baut die Liste der Primzahlen bis Obergrenze auf}

const

MAX = 65536;

var

begin

 

begin

end;

 

end; {PrimfeldAufbauen}

 

var

begin

inc(fFakAnzahl);

with fFaktoren[fFakAnzahl] do

Potenz := 0;

while (Zahl mod inFak) = 0 do

Zahl := Zahl div inFak;

inc(Potenz);

end;

end;

 

var

begin

 

{Suche Teiler von inZahl}

begin

end;

end; {Faktorisierung}

var

begin

if fFakZahl <> n then

Faktorisierung(n);

 

with fFaktoren[i] do

else

with fFaktoren[fFakAnzahl] do

else

write(Faktor);

 

end;

 

procedure tFaktorisieren.TeilerErmitteln;

var

var

begin

i := 0;

repeat

inc(Position);

inc(i);

end;

begin

//Sortieren

j := i;

Position := fTeiler[j];

dec(j);

end;

end;

 

var

begin

cnt := 0;

result := 0;

begin

BREAK;

Teiler := Faktor;

inZahl := inZahl div Teiler;

inc(cnt);

end;

end;

 

var

begin

Faktorisierung(inZahl);

TempBasPer := BasisPeriodeExtrahieren(TempZahl);

TempPer := 0;

Faktorisierung(TempZahl);

TempPhi := fEulerPhi;

Faktorisierung(TempPhi);

i := 0;

repeat

TempPer := fTeiler[i];

Break;

inc(i);

until i >= Length(fTeiler);

end;

 

Faktorisierung(inZahl);

fPeriodenlaenge := TempPer;

end;

 

var

procedure Ziffernfolge(Ende: longint);

begin

while j < 0 do

inc(pText);

 

inc(j);

end;

begin

pText := @OutText[3];

 

Rest := 1;

i := 0;

Ziffernfolge(fStartPeriode);

EXIT;

 

Ziffernfolge(limit);

 

 

 

exit;

end;

 

procedure start;

 

Limit := 500;

 

repeat

if F.Prim(Testzahl) then

begin

F.PeriodeErmitteln(Testzahl);

inc(longPrimCount);

end;

inc(Testzahl);

 

F := tFaktorisieren.create;

writeln('Start');

start;

writeln('Fertig.');

readln;

{{out}}

<pre>sh-4.4# ./Periode

{{trans|Sidef}}

{{libheader|ntheory}}

 

sub is_long_prime {

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:

 

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 {

$t++ if defined $z && $z+1 == $_;

} 8192000;

{{out}}

<pre>206594</pre>

=={{header|Phix}}==

Slow version:

(use the same main() as below but limit maxN to 8 iterations)

 

Much faster version:

{{out}}

slow version:

8192000 is 206594 (1 minute and 60s)

</pre>

 

=={{header|Prolog}}==

{{works with|SWI Prolog}}

long_prime(Prime):-

is_prime(Prime),

 

main:-

 

Module for finding prime numbers up to some limit:

:- dynamic is_prime/1.

 

cross_out(S, N, P):-

Q is S + 2 * P,

 

{{out}}

% 8,564,024 inferences, 0.991 CPU in 1.040 seconds (95% CPU, 8641390 Lips)

true.

</pre>

 

=={{header|Python}}==

{{trans|Kotlin}}

primes = []

c = [False] * (limit + 1) # composite = true

print('\nThe number of long primes up to:')

for (i, total) in enumerate(totals):

{{out}}

<pre>

64000 is 2430

</pre>

 

=={{header|Racket}}==

{{trans|Go}} (at least '''find-period''')

 

(require math/number-theory)

 

(module+ test

(require rackunit)

 

{{out}}

{{works with|Rakudo|2018.06}}

Not very fast as the numbers get larger.

my $sieve = Math::Primesieve.new;

 

say "\nNumber of long primes ≤ $upto: ", +@long-primes;

$from = $upto;

{{out}}

<pre>Long primes ≤ 500:

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===

/*───────────────────── maximal period primes, long period primes, full reptend primes).*/

parse arg a /*obtain optional argument from the CL.*/

.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*/

{{out|output|text=&nbsp; when using the internal default inputs:}}

<pre>

===uses odd numbers, some prime tests===

This REXX version is about &nbsp; '''2''' &nbsp; times faster than the 1^st REXX version &nbsp; (because it does some primality testing).

/*───────────────────── maximal period primes, long period primes, full reptend primes).*/

parse arg a /*obtain optional argument from the CL.*/

.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*/

{{out|output|text=&nbsp; is identical to the 1^st REXX version.}}

 

===uses primes===

This REXX version is about &nbsp; '''5''' &nbsp; times faster than the 1^st REXX version &nbsp; (because it only tests primes).

/*───────────────────── maximal period primes, long period primes, full reptend primes).*/

parse arg a /*obtain optional argument from the CL.*/

.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*/

{{out|output|text=&nbsp; is identical to the 1^st REXX version.}} <br>

 

=={{header|Ruby}}==

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

end

 

 

{{out}}

 

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'

end

 

 

{{out}}

{{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

puts "Number of long primes ≤ #{n}: #{(7..n).count { |pc| long_prime? pc }}"

end

 

{{out}}

 

=={{header|Rust}}==

// References:

// https://en.wikipedia.org/wiki/Full_reptend_prime

 

fn is_long_prime(sieve: &PrimeSieve, prime: usize) -> bool {

if 10 % prime == 0 {

return false;

let mut prime = 3;

while prime < limit2 {

if prime < limit1 {

print!("{} ", prime);

fn main() {

long_primes(500, 8192000);

 

use crate::bit_array;

 

!self.composite.get(n / 2 - 1)

}

 

pub struct BitArray {

array: Vec<u32>,

}

}

 

{{out}}

Number of long primes up to 4096000: 108381

Number of long primes up to 8192000: 206594

</pre>

 

=={{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)) {

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>

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

for key in counts.keys.sorted() {

print("There are \(counts[key]!) long primes less than \(key)")

 

{{out}}

=={{header|Visual Basic .NET}}==

{{trans|C#}}

 

Module LongPrimes

End Function

 

{{out}}

Same output as C#.

{{libheader|Wren-fmt}}

{{libheader|Wren-math}}

// finds the period of the reciprocal of n

var i = 0

for (total in totals) {

i = i + 1

 

{{out}}

{{trans|C}}

{{works with|Windows XBasic}}

PROGRAM "longprimes"

VERSION "0.0002"

 

END PROGRAM

{{out}}

<pre>

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

}

period

 

println("The long primes up to 500 are:\n",longPrimes.filter('<(500)).concat(","));

 

foreach n in (T(500, 1000, 2000, 4000, 8000, 16000, 32000, 64000)){

println(" %5d is %d".fmt( n, longPrimes.filter1n('>(n)) ));

{{out}}

<pre>