Sieve of Pritchard: Difference between revisions
m
→{{header|AppleScript}}: Speeded up.
m (→{{header|Pascal}}: fpc 3.2.2 does the job. My old fpc 3.3.1 can't run " SetLength( smallPrimes, SP_STEP);" , maybe installation problem.) |
m (→{{header|AppleScript}}: Speeded up.) |
||
Line 31:
if (limit < 2) then return {}
script o
property
property
end script
set {x, newCircumference, currentPrime, mv} to {0, 2, 1, missing value}
set prime to 1▼
repeat until (
-- Get the
set
set
--
--
-- It'll be far longer than needed, but hey.
set
set
if (
set o's extension to makeList(newCircumference - oldCircumference, mv)
repeat with augend from oldCircumference to (circumference - 1) by oldCircumference▼
-- Insert numbers that
-- unpartitioned part of the wheel, except where the results are multiples of currentPrime.
set k to 0
set listLen to (count o's wheel)
▲ repeat with augend from oldCircumference to (
set n to augend + 1
if (n mod currentPrime > 0) then
set k to k + 1
set o's extension's item k to n
end if
repeat with i from x to listLen
set n to augend + (o's wheel's item i)
if (n >
if (n mod
set k to k + 1
set o's extension's item k to n
end if
end repeat
end repeat
-- Find and delete multiples of the current prime
set
set i to
repeat while ((o's wheel's item i) <
set i to i + 1
end repeat
repeat with i from i to
set j to binarySearch((o's wheel's item i) *
if (j > 0) then
set o's wheel's item j to
set
end if
end repeat
-- Keep the undeleted numbers and any in the extension list.
set o's wheel to o's wheel's numbers
if (k > 0) then set o's wheel to o's wheel & o's extension's items 1 thru k
end repeat
return
end sieveOfPritchard
on makeList(limit, filler)
if (limit < 1) then return {}
script o
property lst : {filler}
end script
repeat until (counter + counter > limit)
set o's lst to o's lst & o's lst
set counter to counter + counter
end repeat
if (counter < limit) then set o's lst to o's lst & o's lst's items 1 thru (limit - counter)
return o's lst
end makeList
on binarySearch(n, theList, l, r)
Line 79 ⟶ 108:
repeat until (l = r)
set m to (l + r) div 2
if (
set l to m + 1
else
Line 86 ⟶ 115:
end repeat
if (
return 0
end binarySearch
| |||