- Joined
- Dec 12, 2008
- Messages
- 7,385
This is not like all the other primality test functions.
The difference with this one is that it attempts to do a few smart things before it goes for the brute force approach.
Feel free to comment on how silly this is.
The difference with this one is that it attempts to do a few smart things before it goes for the brute force approach.
JASS:
/**************************************
*
* IsPrime
* v1.0.0.0
* By Magtheridon96
*
* - Efficient Primality Test Function
*
* Requires:
* ---------
*
* - Table by Bribe
* - [url]http://www.hiveworkshop.com/forums/jass-resources-412/snippet-new-table-188084/[/url]
*
* API:
* ----
*
* function IsPrime takes integer n returns boolean
* - Determines whether a number is prime or not.
*
**************************************/
library IsPrime requires Table
globals
private integer array pList
private Table prime
private Table done
endglobals
function IsPrime takes integer n returns boolean
local integer i = 0
local integer k = 0
local boolean notFound = true
/*
* Shift to positive integer.
*/
if n < 0 then
set n = -n
endif
/*
* No need to repeat previous computations.
*/
if n <= 100 or done.boolean[n] then
return prime.boolean[n]
endif
set done.boolean[n] = true
/*
* Quick test.
*
* This gets rid of most numbers.
*/
if n/2*2 == 0 or n/3*3 == 0 or n/5*5 == 0 then
set prime.boolean[n] = false
return false
endif
/*
* If the number is not of the form
* 30k + i where i is a prime between
* 1 and 29 not equal to 2, 3 or 5,
* then the number is not prime.
*
* All primes are of this form.
*/
loop
set k = n - pList[i]
if k/30*30 == k then
set notFound = false
exitwhen true
endif
exitwhen i == 7
set i = i + 1
endloop
if notFound then
set prime.boolean[n] = false
return false
endif
/*
* Brute force test.
*
* This is very slow ;_;
*/
set i = 7
set k = R2I(SquareRoot(n))
loop
if n/i*i == n then
set prime.boolean[n] = false
return false
endif
exitwhen i >= k
set i = i + 2
endloop
set prime.boolean[n] = true
return true
endfunction
private module Init
private static method onInit takes nothing returns nothing
set done = Table.create()
set prime = Table.create()
set prime.boolean[0] = true
set prime.boolean[1] = true
set prime.boolean[2] = true
set prime.boolean[3] = true
set prime.boolean[5] = true
set prime.boolean[7] = true
set prime.boolean[11] = true
set prime.boolean[13] = true
set prime.boolean[17] = true
set prime.boolean[19] = true
set prime.boolean[23] = true
set prime.boolean[29] = true
set prime.boolean[31] = true
set prime.boolean[37] = true
set prime.boolean[41] = true
set prime.boolean[43] = true
set prime.boolean[47] = true
set prime.boolean[53] = true
set prime.boolean[59] = true
set prime.boolean[61] = true
set prime.boolean[67] = true
set prime.boolean[71] = true
set prime.boolean[73] = true
set prime.boolean[79] = true
set prime.boolean[83] = true
set prime.boolean[89] = true
set prime.boolean[97] = true
set pList[0] = 1
set pList[1] = 7
set pList[2] = 11
set pList[3] = 13
set pList[4] = 17
set pList[5] = 19
set pList[6] = 23
set pList[7] = 29
endmethod
endmodule
private struct Inits extends array
implement Init
endstruct
endlibraryFeel free to comment on how silly this is.
