Different ways of generating prime numbers

Scripting Forums AppleScript | Mac OS X
#1

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

:smiley:

#2 
-- 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
#3

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!

#4

No worries, Thomas. :slight_smile:

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.

#5

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

#6

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. :cool: