Wieferich primes: Difference between revisions
Content added Content deleted
SqrtNegInf (talk | contribs) (Added Perl) |
(Added Forth solution) |
||
Line 93: | Line 93: | ||
Weiferich primes less than 5000: |
Weiferich primes less than 5000: |
||
V{ 1093 3511 } |
V{ 1093 3511 } |
||
</pre> |
|||
=={{header|Forth}}== |
|||
{{works with|Gforth}} |
|||
<lang forth>: prime? ( n -- ? ) here + c@ 0= ; |
|||
: notprime! ( n -- ) here + 1 swap c! ; |
|||
: prime_sieve { n -- } |
|||
here n erase |
|||
0 notprime! |
|||
1 notprime! |
|||
n 4 > if |
|||
n 4 do i notprime! 2 +loop |
|||
then |
|||
3 |
|||
begin |
|||
dup dup * n < |
|||
while |
|||
dup prime? if |
|||
n over dup * do |
|||
i notprime! |
|||
dup 2* +loop |
|||
then |
|||
2 + |
|||
repeat |
|||
drop ; |
|||
: modpow { c b a -- a^b mod c } |
|||
c 1 = if 0 exit then |
|||
1 |
|||
a c mod to a |
|||
begin |
|||
b 0> |
|||
while |
|||
b 1 and 1 = if |
|||
a * c mod |
|||
then |
|||
a a * c mod to a |
|||
b 2/ to b |
|||
repeat ; |
|||
: wieferich_prime? { p -- ? } |
|||
p prime? if |
|||
p p * p 1- 2 modpow 1 = |
|||
else |
|||
false |
|||
then ; |
|||
: wieferich_primes { n -- } |
|||
." Wieferich primes less than " n 1 .r ." :" cr |
|||
n prime_sieve |
|||
n 0 do |
|||
i wieferich_prime? if |
|||
i 1 .r cr |
|||
then |
|||
loop ; |
|||
5000 wieferich_primes |
|||
bye</lang> |
|||
{{out}} |
|||
<pre> |
|||
Wieferich primes less than 5000: |
|||
1093 |
|||
3511 |
|||
</pre> |
</pre> |
||