# Different ways of generating prime numbers

Due to Bruce Phillips help I could solve my prime number generating script problems up to 90%. The last that is missing is to adapt the “Sieve of Eratosthenes”-algorithm. The script by now looks like this. Open the Event Log window and have a look:

``````-- Different ways to create prime numbers

on run

-- Brute Force Methode 1
repeat with n from 1 to 100
set composite to 0
repeat with i from 2 to (n - 1)
if (n mod i = 0) then set composite to 1
end repeat
if composite = 0 then log n
end repeat

-- Brute Force Methode 2
repeat with n from 1 to 100
set composite to 0
set sqr to intsqrt(n)
repeat with i from 2 to sqr
if (n mod i = 0) then set composite to 1
end repeat
if (composite is 0) then log n
end repeat

-- Primes method originally using the Math Commands osax. Written by ???
local min, max, neverZero, maxDiv, divTry, res

-- Here you can set any range that suits you
set {min, max} to {1, 200}
set res to {}

-- By some people's opinion, 1 is not considered a prime
if min = 1 then set min to 2
-- 2 is special, so it has to be handled in its own way
if min = 2 then set {res, min} to {{2}, 3}
-- We can't use even numbers, because they are never primes, except for 2
if min mod 2 = 0 then set min to min + 1

repeat until min > max
set maxDiv to intsqrt(min)
set {neverZero, divTry} to {true, 3}
repeat until divTry > maxDiv
if min mod divTry = 0 then
set neverZero to false
exit repeat
end if
set divTry to divTry + 2
end repeat
if neverZero then
set res to res & min
log min
end if
set min to min + 2
end repeat

(*

-- The sieve of Eratosthenes

const N = 10000
var canceled: array [2..N] of boolean

{ Initialising the field of primes }
{ All of the number are not part of canceled on beginning }
for i = 2 to N do
canceled[i] = false
end

i = 2
while i*i <= N do
if not canceled[i] then
{ i is a prime, cancel its multiples beginning with i*i }
for j = i*i to N by i do
canceled[j] = true
end
i = i+1
end

for i = 2 to N do
if not canceled[i] then
print i; ", ";
end

*)

end run

on intsqrt(n)
return (do shell script "echo 'sqrt (" & n & " )' | /usr/bin/bc")
end intsqrt

``````

``````-- Sieve of Eratosthenes
set n to 2020

set canceled to {}

-- { Initialising the field of primes }
-- { All of the number are not part of canceled on beginning }
-- This is very slow in AppleScript!!! Be patient on high numbers!
repeat n times
set canceled to canceled & false
end repeat

-- From now on it runs fast!
set i to 2
repeat while i * i â‰¤ n
if item i of canceled is false then
-- { i is a prime, cancel its multiples beginning with i*i }
repeat with j from i * i to n by i
set item j of canceled to true
end repeat
end if
set i to i + 1
end repeat

repeat with i from 2 to n
if item i of canceled is false then log i
end repeat
``````

You may replace intsqrt(n) in the script above with this vanilla code in order to let it run faster:

``````on intsqrt(aNumber)
aNumber ^ 0.5 div 1
end intsqrt
``````

Thanks to Qwerty Denzel and kai for the hint!

No worries, Thomas.

It might be worth clarifying that there are a number of good reasons for using AppleScript’s native mathematical functions, like the exponentiation and div operators, for this sort of situation.

They’re concise, of course. They’re very fast, too - especially when pitched against text manipulations and multiple coercions from number-to-string, string-to-list, list-to-string and string-to-integer.

Another consideration with the text approach is that, if AppleScript’s text item delimiters just happen to be set to a value other than {“”} or “”, one could get spurious results. And if the earlier subroutine was used on a system that defaults to anything other than a comma decimal separator for real numbers, it wouldn’t work too well, either.

Hi, Thomas.

If it’s of any interest to you, there was a discussion of the “Sieve of Eratosthenes” and AppleScript in Code Exchange a few months ago.

http://bbs.applescript.net/viewtopic.php?id=15030

Thanks. As you can see above, I found well working code for the “Sieve of Eratosthenes” and edited the post in order to change “Pytagoras” into “Erotosthenes”. May they both forgive me this mistake.