Rosetta Code

Wieferich primes: Difference between revisions

Page Discussion

Wieferich primes (view source)

Revision as of 10:17, 24 March 2024

15,606 bytes added ,  1 month ago
added RPL
(Added Sidef)
(added RPL)
 
(32 intermediate revisions by 21 users not shown)
Line 1:
{{draft task|Prime Numbers}}
{{Wikipedia|Wieferich prime}}
<br>
Line 19:
;* [[oeis:A001220|OEIS A001220 - Wieferich primes]]
<br>
 
=={{header|Ada}}==
{{trans|BASIC256}}
<syntaxhighlight lang="ada">with Ada.Text_IO;
 
procedure Wieferich_Primes is
 
function Is_Prime (V : Positive) return Boolean is
D : Positive := 5;
begin
if V < 2 then return False; end if;
if V mod 2 = 0 then return V = 2; end if;
if V mod 3 = 0 then return V = 3; end if;
while D * D <= V loop
if V mod D = 0 then
return False;
end if;
D := D + 2;
end loop;
return True;
end Is_Prime;
 
function Is_Wieferich (N : Positive) return Boolean is
Q : Natural := 1;
begin
if not Is_Prime (N) then
return False;
end if;
for P in 2 .. N loop
Q := (2 * Q) mod N**2;
end loop;
return Q = 1;
end Is_Wieferich;
 
begin
 
Ada.Text_IO.Put_Line ("Wieferich primes below 5000:");
for N in 1 .. 4999 loop
if Is_Wieferich (N) then
Ada.Text_IO.Put_Line (N'Image);
end if;
end loop;
 
end Wieferich_Primes;</syntaxhighlight>
{{out}}
<pre>
Wieferich primes below 5000:
1093
3511
</pre>
 
=={{header|ALGOL 68}}==
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}}
{{libheader|ALGOL 68-primes}}
<syntaxhighlight lang="algol68">
BEGIN # find Wierferich Primes: primes p where p^2 evenly divides 2^(p-1)-1 #
 
INT max number = 5 000; # maximum number we will consider #
# set precision of LONG LONG INT - p^5000 has over 1500 digits #
PR precision 1600 PR
PR read "primes.incl.a68" PR # include prime utlities #
# get a list of primes up to max number #
[]INT prime = EXTRACTPRIMESUPTO max number
FROMPRIMESIEVE PRIMESIEVE max number;
 
# find the primes #
INT p pos := LWB prime;
LONG LONG INT two to p minus 1 := 1;
INT power := 0;
INT w count := 0;
WHILE w count < 2 DO
INT p = prime[ p pos ];
WHILE power < ( p - 1 ) DO
two to p minus 1 *:= 2;
power +:= 1
OD;
IF ( two to p minus 1 - 1 ) MOD ( p * p ) = 0 THEN
print( ( " ", whole( p, 0 ) ) );
w count +:= 1
FI;
p pos +:= 1
OD
END
</syntaxhighlight>
{{out}}
<pre>
1093 3511
</pre>
 
=={{header|APL}}==
'''Works in:''' [[Dyalog APL]]
<syntaxhighlight lang="apl"> ⎕CY 'dfns' ⍝ import dfns namespace
⍝ pco ← prime finder
⍝ nats ← natural number arithmetic (uses strings)
⍝ Get all Wieferich primes below n:
wief←{{⍵/⍨{(,'0')≡(×⍨⍵)|nats 1 -nats⍨ 2 *nats ⍵-1}¨⍵}⍸1 pco⍳⍵}
wief 5000
1093 3511
</syntaxhighlight>
=={{header|Arturo}}==
 
<syntaxhighlight lang="rebol">wieferich?: function [n][
and? -> prime? n
-> zero? (dec 2 ^ n-1) % n ^ 2
]
 
print ["Wieferich primes less than 5000:" select 1..5000 => wieferich?]</syntaxhighlight>
 
{{out}}
 
<pre>Wieferich primes less than 5000: [1093 3511]</pre>
 
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f WIEFERICH_PRIMES.AWK
# converted from FreeBASIC
BEGIN {
start = 1
stop = 4999
for (i=start; i<=stop; i++) {
if (is_wieferich_prime(i)) {
printf("%d\n",i)
count++
}
}
printf("Wieferich primes %d-%d: %d\n",start,stop,count)
exit(0)
}
function is_prime(n, d) {
d = 5
if (n < 2) { return(0) }
if (n % 2 == 0) { return(n == 2) }
if (n % 3 == 0) { return(n == 3) }
while (d*d <= n) {
if (n % d == 0) { return(0) }
d += 2
if (n % d == 0) { return(0) }
d += 4
}
return(1)
}
function is_wieferich_prime(p, p2,q) {
if (!is_prime(p)) { return(0) }
q = 1
p2 = p^2
while (p > 1) {
q = (2*q) % p2
p--
}
return(q == 1)
}
</syntaxhighlight>
{{out}}
<pre>
1093
3511
Wieferich primes 1-4999: 2
</pre>
 
=={{header|BASIC}}==
==={{header|BASIC256}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="freebasic">print "Wieferich primes less than 5000: "
for i = 1 to 5000
if isWeiferich(i) then print i
next i
end
 
function isWeiferich(p)
if not isPrime(p) then return False
q = 1
p2 = p ^ 2
while p > 1
q = (2 * q) mod p2
p -= 1
end while
if q = 1 then return True else return False
end function
 
function isPrime(v)
if v < 2 then return False
if v mod 2 = 0 then return v = 2
if v mod 3 = 0 then return v = 3
d = 5
while d * d <= v
if v mod d = 0 then return False else d += 2
end while
return True
end function</syntaxhighlight>
{{out}}
<pre>Igual que la entrada de FreeBASIC.</pre>
 
==={{header|PureBasic}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="purebasic">Procedure.i isPrime(n)
Protected k
If n = 2 : ProcedureReturn #True
ElseIf n <= 1 Or n % 2 = 0 : ProcedureReturn #False
Else
For k = 3 To Int(Sqr(n)) Step 2
If n % k = 0
ProcedureReturn #False
EndIf
Next
EndIf
ProcedureReturn #True
EndProcedure
 
Procedure.i isWeiferich(p)
Protected q, p2
If Not isPrime(p) : ProcedureReturn #False : EndIf
q = 1
p2 = Pow(p, 2)
While p > 1
q = (2*q) % p2
p - 1
Wend
If q = 1
ProcedureReturn #True
Else
ProcedureReturn #False
EndIf
EndProcedure
 
OpenConsole()
PrintN("Wieferich primes less than 5000: ")
For i = 2 To 5000
If isWeiferich(i)
PrintN(Str(i))
EndIf
Next i
Input()
CloseConsole()</syntaxhighlight>
{{out}}
<pre>Igual que la entrada de FreeBASIC.</pre>
 
==={{header|Run BASIC}}===
<syntaxhighlight lang="runbasic">print "Wieferich primes less than 5000: "
for i = 1 to 5000
if isWeiferich(i) then print i
next i
end
 
function isPrime(n)
if n < 2 then isPrime = 0 : goto [exit]
if n = 2 then isPrime = 1 : goto [exit]
if n mod 2 = 0 then isPrime = 0 : goto [exit]
isPrime = 1
for i = 3 to int(n^.5) step 2
if n mod i = 0 then isPrime = 0 : goto [exit]
next i
[exit]
end function
 
function isWeiferich(p)
if isPrime(p) = 0 then isWeiferich = 0 : goto [exit]
q = 1
p2 = p^2
while p > 1
q = (2*q) mod p2
p = p - 1
wend
if q = 1 then
isWeiferich = 1 : goto [exit]
else
isWeiferich = 0 : goto [exit]
end if
[exit]
end function</syntaxhighlight>
{{out}}
<pre>Igual que la entrada de FreeBASIC.</pre>
 
==={{header|Yabasic}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="yabasic">print "Wieferich primes less than 5000: "
for i = 2 to 5000
if isWeiferich(i) print i
next i
end
 
sub isWeiferich(p)
if not isPrime(p) return False
q = 1
p2 = p ^ 2
while p > 1
q = mod((2*q), p2)
p = p - 1
wend
if q = 1 then return True else return False : fi
end sub
 
sub isPrime(v)
if v < 2 return False
if mod(v, 2) = 0 return v = 2
if mod(v, 3) = 0 return v = 3
d = 5
while d * d <= v
if mod(v, d) = 0 then return False else d = d + 2 : fi
wend
return True
end sub</syntaxhighlight>
{{out}}
<pre>Igual que la entrada de FreeBASIC.</pre>
 
 
=={{header|C}}==
{{trans|C++}}
<langsyntaxhighlight lang="c">#include <stdbool.h>
#include <stdio.h>
#include <stdint.h>
Line 91 ⟶ 398:
 
return 0;
}</langsyntaxhighlight>
{{out}}
<pre>Wieferich primes less than 5000:
Line 98 ⟶ 405:
 
=={{header|C++}}==
<langsyntaxhighlight lang="cpp">#include <cstdint>
#include <iostream>
#include <vector>
Line 150 ⟶ 457:
for (uint64_t p : wieferich_primes(limit))
std::cout << p << '\n';
}</langsyntaxhighlight>
 
{{out}}
<pre>
Wieferich primes less than 5000:
1093
3511
</pre>
 
=={{header|C#}}==
{{trans|Java}}
<syntaxhighlight lang="csharp">using System;
using System.Collections.Generic;
using System.Linq;
 
namespace WieferichPrimes {
class Program {
static long ModPow(long @base, long exp, long mod) {
if (mod == 1) {
return 0;
}
 
long result = 1;
@base %= mod;
for (; exp > 0; exp >>= 1) {
if ((exp & 1) == 1) {
result = (result * @base) % mod;
}
@base = (@base * @base) % mod;
}
return result;
}
 
static bool[] PrimeSieve(int limit) {
bool[] sieve = Enumerable.Repeat(true, limit).ToArray();
 
if (limit > 0) {
sieve[0] = false;
}
if (limit > 1) {
sieve[1] = false;
}
 
for (int i = 4; i < limit; i += 2) {
sieve[i] = false;
}
 
for (int p = 3; ; p += 2) {
int q = p * p;
if (q >= limit) {
break;
}
if (sieve[p]) {
int inc = 2 * p;
for (; q < limit; q += inc) {
sieve[q] = false;
}
}
}
 
return sieve;
}
 
static List<int> WiefreichPrimes(int limit) {
bool[] sieve = PrimeSieve(limit);
List<int> result = new List<int>();
for (int p = 2; p < limit; p++) {
if (sieve[p] && ModPow(2, p - 1, p * p) == 1) {
result.Add(p);
}
}
return result;
}
 
static void Main() {
const int limit = 5000;
Console.WriteLine("Wieferich primes less that {0}:", limit);
foreach (int p in WiefreichPrimes(limit)) {
Console.WriteLine(p);
}
}
}
}</syntaxhighlight>
{{out}}
<pre>Wieferich primes less that 5000:
1093
3511</pre>
 
=={{header|EasyLang}}==
{{trans|BASIC256}}
 
<syntaxhighlight>
fastfunc isprim num .
i = 2
while i <= sqrt num
if num mod i = 0
return 0
.
i += 1
.
return 1
.
func wieferich p .
if isprim p = 0
return 0
.
q = 1
p2 = p * p
while p > 1
q = (2 * q) mod p2
p -= 1
.
if q = 1
return 1
.
.
print "Wieferich primes less than 5000: "
for i = 2 to 5000
if wieferich i = 1
print i
.
.
</syntaxhighlight>
 
{{out}}
<pre>
Wieferich primes less than 5000:
1093
3511
Line 161 ⟶ 590:
=={{header|F_Sharp|F#}}==
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_functions Extensible Prime Generator (F#)]
<langsyntaxhighlight lang="fsharp">
// Weiferich primes: Nigel Galloway. June 2nd., 2021
primes32()|>Seq.takeWhile((>)5000)|>Seq.filter(fun n->(2I**(n-1)-1I)%(bigint(n*n))=0I)|>Seq.iter(printfn "%d")
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 171 ⟶ 600:
Real: 00:00:00.004
</pre>
 
=={{header|Factor}}==
{{works with|Factor|0.99 2021-02-05}}
<langsyntaxhighlight lang="factor">USING: io kernel math math.functions math.primes prettyprint
sequences ;
 
"Wieferich primes less than 5000:" print
5000 primes-upto [ [ 1 - 2^ 1 - ] [ sq divisor? ] bi ] filter .</langsyntaxhighlight>
{{out}}
<pre>
Wieferich primes less than 5000:
V{ 1093 3511 }
</pre>
 
=={{header|fermat}}==
<syntaxhighlight lang="fermat">
Func Iswief(p)=Isprime(p)*Divides(p^2, 2^(p-1)-1).
for i=2 to 5000 do if Iswief(i) then !!i fi od
</syntaxhighlight>
{{out}}<pre>
1093
3511
</pre>
 
=={{header|Forth}}==
{{works with|Gforth}}
<langsyntaxhighlight lang="forth">: prime? ( n -- ? ) here + c@ 0= ;
: notprime! ( n -- ) here + 1 swap c! ;
 
Line 240 ⟶ 680:
 
5000 wieferich_primes
bye</langsyntaxhighlight>
 
{{out}}
Line 248 ⟶ 688:
3511
</pre>
 
=={{header|FreeBASIC}}==
<syntaxhighlight lang="freebasic">
#include "isprime.bas"
 
function iswief( byval p as uinteger ) as boolean
if not isprime(p) then return 0
dim as integer q = 1, p2 = p^2
while p>1
q=(2*q) mod p2
p = p - 1
wend
if q=1 then return 1 else return 0
end function
 
for i as uinteger = 1 to 5000
if iswief(i) then print i
next i</syntaxhighlight>
 
=={{header|Go}}==
{{trans|Wren}}
{{libheader|Go-rcu}}
<langsyntaxhighlight lang="go">package main
 
import (
Line 275 ⟶ 733:
}
}
}</langsyntaxhighlight>
 
{{out}}
Line 283 ⟶ 741:
3,511
</pre>
 
=={{header|Haskell}}==
<syntaxhighlight lang="haskell">isPrime :: Integer -> Bool
isPrime n
|n == 2 = True
|n == 1 = False
|otherwise = null $ filter (\i -> mod n i == 0 ) [2 .. root]
where
root :: Integer
root = toInteger $ floor $ sqrt $ fromIntegral n
 
isWieferichPrime :: Integer -> Bool
isWieferichPrime n = isPrime n && mod ( 2 ^ ( n - 1 ) - 1 ) ( n ^ 2 ) == 0
 
solution :: [Integer]
solution = filter isWieferichPrime [2 .. 5000]
 
main :: IO ( )
main = do
putStrLn "Wieferich primes less than 5000:"
print solution</syntaxhighlight>
{{out}}
<pre>Wieferich primes less than 5000:
[1093,3511]</pre>
 
 
=={{header|J}}==
<syntaxhighlight lang="j"> I.(1&p: * 0=*: | _1+2x^<:) i.5000
1093 3511</syntaxhighlight>
 
About 12 times faster:
 
<syntaxhighlight lang="j"> p: I. (0=*:|_1+2x^<:) I.1 p: i.5000
1093 3511</syntaxhighlight>
 
=={{header|Java}}==
{{trans|C++}}
<langsyntaxhighlight lang="java">import java.util.*;
 
public class WieferichPrimes {
Line 340 ⟶ 832:
return result;
}
}</langsyntaxhighlight>
 
{{out}}
<pre>
Wieferich primes less than 5000:
1093
3511
</pre>
 
=={{header|jq}}==
'''Works with gojq, the Go implementation of jq'''
 
gojq supports unbounded-precision integer arithmetic and so is up to this task.
<syntaxhighlight lang="jq">def is_prime:
. as $n
| if ($n < 2) then false
elif ($n % 2 == 0) then $n == 2
elif ($n % 3 == 0) then $n == 3
elif ($n % 5 == 0) then $n == 5
elif ($n % 7 == 0) then $n == 7
elif ($n % 11 == 0) then $n == 11
elif ($n % 13 == 0) then $n == 13
elif ($n % 17 == 0) then $n == 17
elif ($n % 19 == 0) then $n == 19
else {i:23}
| until( (.i * .i) > $n or ($n % .i == 0); .i += 2)
| .i * .i > $n
end;
 
# Emit an array of primes less than `.`
def primes:
if . < 2 then []
else
[2] + [range(3; .; 2) | select(is_prime)]
end;
 
# for the sake of infinite-precision integer arithmetic
def power($b): . as $a | reduce range(0; $b) as $i (1; .*$a);
</syntaxhighlight>
'''The task'''
<syntaxhighlight lang="jq"># Input: the limit
def wieferich:
primes[]
| . as $p
| select( ( (2|power($p-1)) - 1) % (.*.) == 0);
 
5000 | wieferich
</syntaxhighlight>
{{out}}
<pre>
1093
3511
Line 350 ⟶ 887:
 
=={{header|Julia}}==
<langsyntaxhighlight lang="julia">using Primes
 
println(filter(p -> (big"2"^(p - 1) - 1) % p^2 == 0, primes(5000))) # [1093, 3511]
</syntaxhighlight>
</lang>
 
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">ClearAll[WieferichPrimeQ]
WieferichPrimeQ[n_Integer] := PrimeQ[n] && Divisible[2^(n - 1) - 1, n^2]
Select[Range[5000], WieferichPrimeQ]</syntaxhighlight>
{{out}}
<pre>{1093, 3511}</pre>
 
=={{header|Nim}}==
{{libheader|bignum}}
<langsyntaxhighlight Nimlang="nim">import math
import bignum
 
Line 376 ⟶ 920:
if p.isPrime:
if exp(two, p - 1, p * p) == 1: # Modular exponentiation.
echo p</langsyntaxhighlight>
 
{{out}}
<pre>Wieferich primes less than 5000:
1093
3511</pre>
 
=={{header|PARI/GP}}==
<syntaxhighlight lang="parigp">iswief(p)=if(isprime(p)&&(2^(p-1)-1)%p^2==0,1,0)
for(N=1,5000,if(iswief(N),print(N)))</syntaxhighlight>
{{out}}<pre>1093
3511</pre>
 
=={{header|Perl}}==
{{libheader|ntheory}}
<langsyntaxhighlight lang="perl">use feature 'say';
use ntheory qw(is_prime powmod);
use bignum;
use ntheory 'is_prime';
 
say 'Wieferich primes less than 5000: ' . join ', ', grep { is_prime($_) and not powmod(2, (2**($_-1) -1) %, $_**2$_) )== 1 } 1..5000;</langsyntaxhighlight>
{{out}}
<pre>Wieferich primes less than 5000: 1093, 3511</pre>
Line 395 ⟶ 944:
=={{header|Phix}}==
 
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
Line 405 ⟶ 954:
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Weiferich primes less than 5000: %V\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">filter</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">get_primes_le</span><span style="color: #0000FF;">(</span><span style="color: #000000;">5000</span><span style="color: #0000FF;">),</span><span style="color: #000000;">weiferich</span><span style="color: #0000FF;">)})</span>
<!--</langsyntaxhighlight>-->
 
{{out}}
Line 412 ⟶ 961:
</pre>
alternative (same results), should be significantly faster, in the (largely pointless!) hunt for larger numbers.
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
Line 423 ⟶ 972:
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Weiferich primes less than 5000: %V\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">filter</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">get_primes_le</span><span style="color: #0000FF;">(</span><span style="color: #000000;">5000</span><span style="color: #0000FF;">),</span><span style="color: #000000;">weiferich</span><span style="color: #0000FF;">)})</span>
<!--</langsyntaxhighlight>-->
 
=={{header|PicoLisp}}==
<syntaxhighlight lang="picolisp">(de **Mod (X Y N)
(let M 1
(loop
(when (bit? 1 Y)
(setq M (% (* M X) N)) )
(T (=0 (setq Y (>> 1 Y)))
M )
(setq X (% (* X X) N)) ) ) )
(let (D 2 L (1 2 2 . (4 2 4 2 4 6 2 6 .)))
(until (> D 5000)
(and
(=1 (**Mod 2 (dec D) (* D D)))
(println D) )
(inc 'D (++ L)) ) )</syntaxhighlight>
{{out}}
<pre>
1093
3511
</pre>
 
=={{header|Python}}==
<syntaxhighlight lang="python">
# Wieferich-Primzahlen
MAX: int = 5_000
 
# Berechnet a^n mod m
def pow_mod(a: int, n: int, m: int) -> int:
assert n >= 0 and m != 0, "pow_mod(a, n, m), n >= 0, m <> 0"
res: int = 1
a %= m
while n > 0:
if n%2:
res = (res*a)%m
n -= 1
else:
a = (a*a)%m
n //= 2
return res%m
 
def is_prime(n: int) -> bool:
for i in range(2, int(n**0.5) + 1):
if n%i == 0:
return False
return True
 
def is_wieferich(p: int) -> True:
if is_prime(p) == False:
return False
if pow_mod(2, p - 1, p*p) == 1:
return True
else:
return False
 
if __name__ == '__main__':
print(f"Wieferich primes less than {MAX}:")
for i in range(2, MAX + 1):
if is_wieferich(i):
print(i)
</syntaxhighlight>
{{out}}
<pre>Wieferich primes less than 5000:
1093
3511</pre>
 
=={{header|Quackery}}==
Line 429 ⟶ 1,043:
<code>eratosthenes</code> and <code>isprime</code> are defined at [[Sieve of Eratosthenes#Quackery]].
 
<langsyntaxhighlight Quackerylang="quackery"> 5000 eratosthenes
[ dup isprime iff
Line 437 ⟶ 1,051:
else [ drop false ] ] is wieferich ( n --> b )
5000 times [ i^ wieferich if [ i^ echo cr ] ]</langsyntaxhighlight>
 
{{out}}
Line 445 ⟶ 1,059:
</pre>
 
 
=={{header|Racket}}==
 
<syntaxhighlight lang="racket">#lang typed/racket
(require math/number-theory)
 
(: wieferich-prime? (-> Positive-Integer Boolean))
 
(define (wieferich-prime? p)
(and (prime? p)
(divides? (* p p) (sub1 (expt 2 (sub1 p))))))
 
(module+ main
(define wieferich-primes<5000
(for/list : (Listof Integer) ((p (sequence-filter wieferich-prime?
(in-range 1 5000))))
p))
wieferich-primes<5000)
</syntaxhighlight>
 
{{out}}
<pre>'(1093 3511)</pre>
 
=={{header|Raku}}==
<syntaxhighlight lang="raku" perl6line>put "Wieferich primes less than 5000: ", join ', ', ^5000 .grep: { .is-prime and not ( exp($_-1, 2) - 1 ) % .² };</langsyntaxhighlight>
{{out}}
<pre>Wieferich primes less than 5000: 1093, 3511</pre>
 
=={{header|REXX}}==
<langsyntaxhighlight lang="rexx">/*REXX program finds and displays Wieferich primes which are under a specified limit N*/
parse arg n . /*obtain optional argument from the CL.*/
if n=='' | n=="," then n= 5000 /*Not specified? Then use the default.*/
numeric digits 3000 /*bump # of dec. digs for calculation. */
numeric digits max(9, length(2**n) ) /*calculate # of decimal digits needed.*/
call genP /*build array of semaphores for primes.*/
title= ' Wieferich primes that are < ' commas(n) /*title for the output. */
w= length(title) + 2 /*width of field for the primes listed.*/
say ' index │'center(title, w) /*display the title for the output. */
say '───────┼'center("" , w, '─') /* " a sep for the" " " output. */
wpfound= 0 /*initialize number of Wieferich primes*/
do j=1 to #; p= @.j; pm= p - 1 /*search for Wieferich primes in range.*/
if (2**pm (p-1)- 1) // p**2\==0 then iterate /*P**2 not evenly divide 2**(P-1) - 1?*/ /* ◄■■■■■■■ the filter.*/
wp found= wpfound + 1 /*bump the counter of Wieferich primes.*/
say center(wpfound, 7)'│' center(commas(p), w) /*display the Wieferich prime to term. */
end /*j*/
 
say '───────┴'center("" , w, '─'); say /*display a foot sep for the output. */
say 'Found ' commas(found) title /* " " summary " " " */
say
say 'Found ' commas(wp) title
exit 0 /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ?
/*──────────────────────────────────────────────────────────────────────────────────────*/
genP: !.= 0 @.1=2; @.2=3; @.3=5; @.4=7; @.5=11 /*placeholdersdefine forsome low primes (semaphoresindex-1). */
@!.1=20; @!.2=31; @!.3=51; @!.45=71; @!.57=1; !.11=1 /* /*define" some low primes. " " " (semaphores).*/
!.2=1; !.3=1; !.5=1; !.7=1; !.11=1 /* " "#= 5; "sq.#= @.# ** 2 "/*number of primes so flags. far; prime². */
do j=@.#+2 by 2 to #=5n-1; parse var j s.#='' @.# **2-1 _ /*numberget ofright primesdecimal sodigit far;of prime²J. */
if _==5 then iterate /*J [↓] generate÷ moreby 5? primes ≤ Yes, highskip.*/
doif j//3==@.#+2 by 2 to n-1 0 then iterate; if j//7==0 then iterate /*find" odd" primes from" here on.3? J ÷ by 7? */
parse var j '' -1 _; if do k=5 while _sq.k<==5j then iterate /*J divisible[↓] divide by 5?the known (rightodd dig)primes.*/
if j// 3@.k==0 then iterate j /*" "/*Is J ÷ a " 3P? Then not prime. ___ */
if j// 7==0 then iterate /*" " " 7? */
/* [↑] the above five lines saves time*/
do k=5 while s.k<=j /* [↓] divide by the known odd primes.*/
if j // @.k == 0 then iterate j /*Is J ÷ X? Then not prime. ___ */
end /*k*/ /* [↑] only process numbers ≤ √ J */
#= #+1; @.#= j; ssq.#= j*j; !.j= 1 /*bump # of Ps; assign next P; P P²sqare; P# .*/
end /*j*/; return</langsyntaxhighlight>
{{out|output|text=&nbsp; when using the default input:}}
<pre>
Line 500 ⟶ 1,131:
 
Found 2 Wieferich primes that are < 5,000
</pre>
 
=={{header|RPL}}==
{{works with|RPL|HP49-C}}
« { } 2
'''WHILE''' DUP 5000 < '''REPEAT'''
'''IF''' 2 OVER 1 - ^ 1 - OVER SQ MOD NOT '''THEN''' SWAP OVER + SWAP '''END'''
NEXTPRIME
'''END''' DROP
» '<span style="color:blue">TASK</span>' STO
{{out}}
<pre>
1: { 1093 3511 }
</pre>
 
=={{header|Ruby}}==
<syntaxhighlight lang="ruby">require "prime"
 
puts Prime.each(5000).select{|p| 2.pow(p-1 ,p*p) == 1 }
</syntaxhighlight>
{{out}}
<pre>1093
3511
</pre>
 
=={{header|Rust}}==
<langsyntaxhighlight lang="rust">// [dependencies]
// primal = "0.3"
// mod_exp = "1.0"
Line 519 ⟶ 1,173:
println!("{}", p);
}
}</langsyntaxhighlight>
 
{{out}}
Line 529 ⟶ 1,183:
 
=={{header|Sidef}}==
<langsyntaxhighlight lang="ruby">func is_wieferich_prime(p, base=2) {
powmod(base, p-1, p**2) == 1
}
 
say ("Wieferich primes less than 5000: ", 5000.primes.grep(is_wieferich_prime))</langsyntaxhighlight>
{{out}}
<pre>
Line 541 ⟶ 1,195:
=={{header|Swift}}==
{{trans|C++}}
<langsyntaxhighlight lang="swift">func primeSieve(limit: Int) -> [Bool] {
guard limit > 0 else {
return []
Line 606 ⟶ 1,260:
for p in wieferichPrimes(limit: limit) {
print(p)
}</langsyntaxhighlight>
 
{{out}}
Line 618 ⟶ 1,272:
{{libheader|Wren-math}}
{{libheader|Wren-big}}
<langsyntaxhighlight ecmascriptlang="wren">import "./math" for Int
import "./big" for BigInt
 
var primes = Int.primeSieve(5000)
Line 627 ⟶ 1,281:
var den = p * p
if (num % den == 0) System.print(p)
}</langsyntaxhighlight>
 
{{out}}
Aerobar
1,150

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/312500...362760"