Long primes: Difference between revisions
Content added Content deleted
m (Minor edit to Rust code) |
(Added Forth solution) |
||
Line 654: | Line 654: | ||
1300 long primes <= 32000 |
1300 long primes <= 32000 |
||
2430 long primes <= 64000 |
2430 long primes <= 64000 |
||
</pre> |
|||
=={{header|Forth}}== |
|||
The prime sieve code was borrowed from [[Sieve of Eratosthenes#Forth]]. |
|||
<lang forth>: prime? ( n -- ? ) here + c@ 0= ; |
|||
: notprime! ( n -- ) here + 1 swap c! ; |
|||
: sieve ( n -- ) |
|||
here over erase |
|||
0 notprime! |
|||
1 notprime! |
|||
2 |
|||
begin |
|||
2dup dup * > |
|||
while |
|||
dup prime? if |
|||
2dup dup * do |
|||
i notprime! |
|||
dup +loop |
|||
then |
|||
1+ |
|||
repeat |
|||
2drop ; |
|||
: modpow ( n1 n2 n3 -- n ) |
|||
dup 1 = if 2drop drop 0 exit then |
|||
1 >r |
|||
rot over mod -rot |
|||
begin |
|||
over 0> |
|||
while |
|||
over 1 and 1 = if |
|||
2 pick r> * over mod >r |
|||
then |
|||
rot dup * over mod -rot |
|||
swap 2/ swap |
|||
repeat |
|||
2drop drop r> ; |
|||
: modpow10 ( n1 n2 -- n ) |
|||
10 -rot modpow ; |
|||
: divide_out ( n1 n2 -- n ) |
|||
begin |
|||
2dup mod 0= |
|||
while |
|||
tuck / swap |
|||
repeat drop ; |
|||
: long_prime? ( n -- ? ) |
|||
dup prime? invert if drop false exit then |
|||
10 over mod 0= if drop false exit then |
|||
dup 1- |
|||
2 >r |
|||
begin |
|||
over r@ dup * > |
|||
while |
|||
r@ prime? if |
|||
dup r@ mod 0= if |
|||
over dup 1- r@ / swap modpow10 1 = if |
|||
2drop rdrop false exit |
|||
then |
|||
r@ divide_out |
|||
then |
|||
then |
|||
r> 1+ >r |
|||
repeat |
|||
rdrop |
|||
dup 1 = if 2drop true exit then |
|||
over 1- swap / swap modpow10 1 <> ; |
|||
: next_long_prime ( n -- n ) |
|||
begin 2 + dup long_prime? until ; |
|||
500 constant limit1 |
|||
512000 constant limit2 |
|||
: main |
|||
limit2 1+ sieve |
|||
limit2 limit1 3 |
|||
0 >r |
|||
." Long primes up to " over 1 .r ." :" cr |
|||
begin |
|||
2 pick over > |
|||
while |
|||
next_long_prime |
|||
dup limit1 < if dup . then |
|||
dup 2 pick > if |
|||
over limit1 = if cr then |
|||
." Number of long primes up to " over 6 .r ." : " r@ 5 .r cr |
|||
swap 2* swap |
|||
then |
|||
r> 1+ >r |
|||
repeat |
|||
2drop drop rdrop ; |
|||
main |
|||
bye</lang> |
|||
{{out}} |
|||
<pre> |
|||
Long primes up to 500: |
|||
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 |
|||
Number of long primes up to 500: 35 |
|||
Number of long primes up to 1000: 60 |
|||
Number of long primes up to 2000: 116 |
|||
Number of long primes up to 4000: 218 |
|||
Number of long primes up to 8000: 390 |
|||
Number of long primes up to 16000: 716 |
|||
Number of long primes up to 32000: 1300 |
|||
Number of long primes up to 64000: 2430 |
|||
Number of long primes up to 128000: 4498 |
|||
Number of long primes up to 256000: 8434 |
|||
Number of long primes up to 512000: 15920 |
|||
</pre> |
</pre> |
||