Rosetta Code

Wieferich primes: Difference between revisions

Page Discussion

Wieferich primes (view source)

Revision as of 10:17, 24 March 2024

6,315 bytes added ,  1 month ago
added RPL
m (Promote. multiple implementations, no questions)
(added RPL)
 
(13 intermediate revisions by 10 users not shown)
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]]
<langsyntaxhighlight lang="apl"> ⎕CY 'dfns' ⍝ import dfns namespace
⍝ pco ← prime finder
⍝ nats ← natural number arithmetic (uses strings)
Line 29 ⟶ 117:
wief 5000
1093 3511
</syntaxhighlight>
</lang>
=={{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">
<lang AWK>
# syntax: GAWK -f WIEFERICH_PRIMES.AWK
# converted from FreeBASIC
Line 69 ⟶ 170:
return(q == 1)
}
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 76 ⟶ 177:
Wieferich primes 1-4999: 2
</pre>
 
=={{header|BASIC}}==
==={{header|BASIC256}}===
{{trans|FreeBASIC}}
<langsyntaxhighlight lang="freebasic">print "Wieferich primes less than 5000: "
for i = 1 to 5000
if isWeiferich(i) then print i
Line 105 ⟶ 207:
end while
return True
end function</langsyntaxhighlight>
{{out}}
<pre>Igual que la entrada de FreeBASIC.</pre>
Line 111 ⟶ 213:
==={{header|PureBasic}}===
{{trans|FreeBASIC}}
<langsyntaxhighlight PureBasiclang="purebasic">Procedure.i isPrime(n)
Protected k
Line 152 ⟶ 254:
Next i
Input()
CloseConsole()</langsyntaxhighlight>
{{out}}
<pre>Igual que la entrada de FreeBASIC.</pre>
 
==={{header|Run BASIC}}===
<langsyntaxhighlight lang="runbasic">print "Wieferich primes less than 5000: "
for i = 1 to 5000
if isWeiferich(i) then print i
Line 188 ⟶ 290:
end if
[exit]
end function</langsyntaxhighlight>
{{out}}
<pre>Igual que la entrada de FreeBASIC.</pre>
Line 194 ⟶ 296:
==={{header|Yabasic}}===
{{trans|FreeBASIC}}
<langsyntaxhighlight lang="yabasic">print "Wieferich primes less than 5000: "
for i = 2 to 5000
if isWeiferich(i) print i
Line 220 ⟶ 322:
wend
return True
end sub</langsyntaxhighlight>
{{out}}
<pre>Igual que la entrada de FreeBASIC.</pre>
Line 227 ⟶ 329:
=={{header|C}}==
{{trans|C++}}
<langsyntaxhighlight lang="c">#include <stdbool.h>
#include <stdio.h>
#include <stdint.h>
Line 296 ⟶ 398:
 
return 0;
}</langsyntaxhighlight>
{{out}}
<pre>Wieferich primes less than 5000:
Line 303 ⟶ 405:
 
=={{header|C++}}==
<langsyntaxhighlight lang="cpp">#include <cstdint>
#include <iostream>
#include <vector>
Line 355 ⟶ 457:
for (uint64_t p : wieferich_primes(limit))
std::cout << p << '\n';
}</langsyntaxhighlight>
 
{{out}}
Line 366 ⟶ 468:
=={{header|C#}}==
{{trans|Java}}
<langsyntaxhighlight lang="csharp">using System;
using System.Collections.Generic;
using System.Linq;
Line 437 ⟶ 539:
}
}
}</langsyntaxhighlight>
{{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
</pre>
 
=={{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 458 ⟶ 603:
=={{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>
Line 470 ⟶ 615:
 
=={{header|fermat}}==
<langsyntaxhighlight 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>
</lang>
{{out}}<pre>
1093
Line 481 ⟶ 626:
=={{header|Forth}}==
{{works with|Gforth}}
<langsyntaxhighlight lang="forth">: prime? ( n -- ? ) here + c@ 0= ;
: notprime! ( n -- ) here + 1 swap c! ;
 
Line 535 ⟶ 680:
 
5000 wieferich_primes
bye</langsyntaxhighlight>
 
{{out}}
Line 545 ⟶ 690:
 
=={{header|FreeBASIC}}==
<langsyntaxhighlight lang="freebasic">
#include "isprime.bas"
 
Line 560 ⟶ 705:
for i as uinteger = 1 to 5000
if iswief(i) then print i
next i</langsyntaxhighlight>
 
=={{header|Go}}==
{{trans|Wren}}
{{libheader|Go-rcu}}
<langsyntaxhighlight lang="go">package main
 
import (
Line 588 ⟶ 733:
}
}
}</langsyntaxhighlight>
 
{{out}}
Line 596 ⟶ 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 653 ⟶ 832:
return result;
}
}</langsyntaxhighlight>
 
{{out}}
Line 666 ⟶ 845:
 
gojq supports unbounded-precision integer arithmetic and so is up to this task.
<langsyntaxhighlight lang="jq">def is_prime:
. as $n
| if ($n < 2) then false
Line 691 ⟶ 870:
# for the sake of infinite-precision integer arithmetic
def power($b): . as $a | reduce range(0; $b) as $i (1; .*$a);
</syntaxhighlight>
</lang>
'''The task'''
<langsyntaxhighlight lang="jq"># Input: the limit
def wieferich:
primes[]
Line 700 ⟶ 879:
 
5000 | wieferich
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 708 ⟶ 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}}==
<langsyntaxhighlight Mathematicalang="mathematica">ClearAll[WieferichPrimeQ]
WieferichPrimeQ[n_Integer] := PrimeQ[n] && Divisible[2^(n - 1) - 1, n^2]
Select[Range[5000], WieferichPrimeQ]</langsyntaxhighlight>
{{out}}
<pre>{1093, 3511}</pre>
Line 722 ⟶ 901:
=={{header|Nim}}==
{{libheader|bignum}}
<langsyntaxhighlight Nimlang="nim">import math
import bignum
 
Line 741 ⟶ 920:
if p.isPrime:
if exp(two, p - 1, p * p) == 1: # Modular exponentiation.
echo p</langsyntaxhighlight>
 
{{out}}
Line 749 ⟶ 928:
 
=={{header|PARI/GP}}==
<langsyntaxhighlight 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)))</langsyntaxhighlight>
{{out}}<pre>1093
3511</pre>
Line 756 ⟶ 935:
=={{header|Perl}}==
{{libheader|ntheory}}
<langsyntaxhighlight lang="perl">use feature 'say';
use ntheory qw(is_prime powmod);
 
say 'Wieferich primes less than 5000: ' . join ', ', grep { is_prime($_) and powmod(2, $_-1, $_*$_) == 1 } 1..5000;</langsyntaxhighlight>
{{out}}
<pre>Wieferich primes less than 5000: 1093, 3511</pre>
Line 765 ⟶ 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 775 ⟶ 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 782 ⟶ 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 793 ⟶ 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}}==
<langsyntaxhighlight PicoLisplang="picolisp">(de **Mod (X Y N)
(let M 1
(loop
Line 809 ⟶ 988:
(=1 (**Mod 2 (dec D) (* D D)))
(println D) )
(inc 'D (++ L)) ) )</langsyntaxhighlight>
{{out}}
<pre>
Line 817 ⟶ 996:
 
=={{header|Python}}==
<syntaxhighlight lang ="python">#!/usr/bin/python
# Wieferich-Primzahlen
MAX: int = 5_000
 
# Berechnet a^n mod m
def isPrime(n):
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 isWeiferichis_wieferich(p: int) -> True:
if not isPrimeis_prime(p) == False:
return False
qif pow_mod(2, p - 1, p*p) == 1:
p2 = p ** 2
while p > 1:
q = (2 * q) % p2
p -= 1
if q == 1:
return True
else:
return False
 
 
if __name__ == '__main__':
print(f"Wieferich primes less than 5000{MAX}: ")
for i in range(2, 5001MAX + 1):
if isWeiferichis_wieferich(i):
print(i)</lang>
</syntaxhighlight>
{{out}}
<pre>Wieferich primes less than 5000:
Line 853 ⟶ 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 861 ⟶ 1,051:
else [ drop false ] ] is wieferich ( n --> b )
5000 times [ i^ wieferich if [ i^ echo cr ] ]</langsyntaxhighlight>
 
{{out}}
Line 869 ⟶ 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.*/
Line 909 ⟶ 1,121:
end /*k*/ /* [↑] only process numbers ≤ √ J */
#= #+1; @.#= j; sq.#= j*j; !.j= 1 /*bump # Ps; assign next P; P sqare; P.*/
end /*j*/; return</langsyntaxhighlight>
{{out|output|text=&nbsp; when using the default input:}}
<pre>
Line 919 ⟶ 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}}==
<langsyntaxhighlight lang="ruby">require "prime"
 
puts Prime.each(5000).select{|p| 2.pow(p-1 ,p*p) == 1 }
</syntaxhighlight>
</lang>
{{out}}
<pre>1093
Line 932 ⟶ 1,157:
 
=={{header|Rust}}==
<langsyntaxhighlight lang="rust">// [dependencies]
// primal = "0.3"
// mod_exp = "1.0"
Line 948 ⟶ 1,173:
println!("{}", p);
}
}</langsyntaxhighlight>
 
{{out}}
Line 958 ⟶ 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 970 ⟶ 1,195:
=={{header|Swift}}==
{{trans|C++}}
<langsyntaxhighlight lang="swift">func primeSieve(limit: Int) -> [Bool] {
guard limit > 0 else {
return []
Line 1,035 ⟶ 1,260:
for p in wieferichPrimes(limit: limit) {
print(p)
}</langsyntaxhighlight>
 
{{out}}
Line 1,047 ⟶ 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 1,056 ⟶ 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/312519...362760"