Long primes: Difference between revisions
Content added Content deleted
m (Forth - rewrote modpow to use locals) |
(Added AppleScript.) |
||
Line 124: | Line 124: | ||
64000 is 2430 |
64000 is 2430 |
||
</pre> |
</pre> |
||
=={{header|AppleScript}}== |
|||
The isLongPrime(n) handler here is a translation of the faster [https://www.rosettacode.org/wiki/Long_primes#Phix Phix] one. |
|||
<lang applescript>on sieveOfEratosthenes(limit) |
|||
script o |
|||
property numberList : {missing value} |
|||
end script |
|||
repeat with n from 2 to limit |
|||
set end of o's numberList to n |
|||
end repeat |
|||
repeat with n from 2 to (limit ^ 0.5 div 1) |
|||
if (item n of o's numberList is n) then |
|||
repeat with multiple from (n * n) to limit by n |
|||
set item multiple of o's numberList to missing value |
|||
end repeat |
|||
end if |
|||
end repeat |
|||
return o's numberList's numbers |
|||
end sieveOfEratosthenes |
|||
on factors(n) |
|||
set output to {} |
|||
if (n < 0) then set n to -n |
|||
set sqrt to n ^ 0.5 |
|||
set limit to sqrt div 1 |
|||
if (limit = sqrt) then |
|||
set end of output to limit |
|||
set limit to limit - 1 |
|||
end if |
|||
repeat with i from limit to 1 by -1 |
|||
if (n mod i is 0) then |
|||
set beginning of output to i |
|||
set end of output to n div i |
|||
end if |
|||
end repeat |
|||
return output |
|||
end factors |
|||
on isLongPrime(n) |
|||
if (n < 3) then return false |
|||
script o |
|||
property f : factors(n - 1) |
|||
end script |
|||
set counter to 0 |
|||
repeat with fi in o's f |
|||
set fi to fi's contents |
|||
set e to 1 |
|||
set base to 10 |
|||
repeat until (fi = 0) |
|||
if (fi mod 2 = 1) then set e to e * base mod n |
|||
set base to base * base mod n |
|||
set fi to fi div 2 |
|||
end repeat |
|||
if (e = 1) then |
|||
set counter to counter + 1 |
|||
if (counter > 1) then exit repeat |
|||
end if |
|||
end repeat |
|||
return (counter = 1) |
|||
end isLongPrime |
|||
-- Task code: |
|||
on longPrimesTask() |
|||
script o |
|||
-- The isLongPrime() handler above returns the correct result for any number |
|||
-- passed to it, but feeeding it only primes in the first place speeds things up. |
|||
property primes : sieveOfEratosthenes(64000) |
|||
property longs : {} |
|||
end script |
|||
set output to {} |
|||
set counter to 0 |
|||
set mileposts to {500, 1000, 2000, 4000, 8000, 16000, 32000, 64000} |
|||
set m to 1 |
|||
set nextMilepost to beginning of mileposts |
|||
set astid to AppleScript's text item delimiters |
|||
repeat with p in o's primes |
|||
set p to p's contents |
|||
if (isLongPrime(p)) then |
|||
-- p being odd, it's never exactly one of the even mileposts. |
|||
if (p < 500) then |
|||
set end of o's longs to p |
|||
else if (p > nextMilepost) then |
|||
if (nextMilepost = 500) then |
|||
set AppleScript's text item delimiters to space |
|||
set end of output to "Long primes up to 500:" |
|||
set end of output to o's longs as text |
|||
end if |
|||
set end of output to "Number of long primes up to " & nextMilepost & ": " & counter |
|||
set m to m + 1 |
|||
set nextMilepost to item m of mileposts |
|||
end if |
|||
set counter to counter + 1 |
|||
end if |
|||
end repeat |
|||
set end of output to "Number of long primes up to " & nextMilepost & ": " & counter |
|||
set AppleScript's text item delimiters to linefeed |
|||
set output to output as text |
|||
set AppleScript's text item delimiters to astid |
|||
return output |
|||
end longPrimesTask |
|||
longPrimesTask()</lang> |
|||
{{output}} |
|||
<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"</pre> |
|||
=={{header|C}}== |
=={{header|C}}== |