[JASS] Prime Number

[priest170234]

Okay, someone review this function for me! (First time coding something by myself in JASS/vJASS without other people's help!)
And please tell me whether is it in JASS or vJASS. I don't see the difference between them.

scope CheckPrime
    globals 
        integer int                 //Constant, does not change at ALL until checked = false
        integer int_2               //Changes
        boolean checked = false
        boolean isPrime
    endglobals

    function CheckPrime takes integer number returns boolean
        if(number<=1) then
            call BJDebugMsg("Please enter a value larger than 1!")
            set isPrime = false
        else
            ////////////////////////////////////////////
            if(checked == false) then
                set checked = true
                set int = number
            endif
            ////////////////////////////////////////////
            set int_2 = number
        
            if (ModuloInteger(int, int_2) == 0) and (int != int_2) then //Divisible, and int not equal to int_2, NOT PRIME
                set int_2 = 0
            endif
        
            if (int_2 == 0) then        //If Its not a Prime Number
                call BJDebugMsg(I2S(int)+" is NOT Prime!") 
                set checked = false
                set isPrime = false
            else                        //Checking...
                if(int_2-1 == 1) then   //If the next number becomes 1, and so far it still prime, then the number IS PRIME!
                    call BJDebugMsg(I2S(int)+" IS Prime!") 
                    set checked = false
                    set isPrime = true
                else
                    set int_2 = int_2 - 1
                    call CheckPrime(int_2)
                endif
            endif
        endif
        if(isPrime == true) then
            return true
        else
            return false
        endif
    endfunction

endscope

 

[Bribe]

It's vJass.

Whenever you see something with "globals" "scope" "library" "struct" or that has grey highlighting, it is vJass.

This needs to be in different threads in case the number is super high. Let me see if I can find a better solution for you.

 

[priest170234]

It's vJass.

Whenever you see something with "globals" "scope" "library" "struct" or that has grey highlighting, it is vJass.

This needs to be in different threads in case the number is super high. Let me see if I can find a better solution for you.

Thanks for telling that!
About

This needs to be in different threads in case the number is super high. Let me see if I can find a better solution for you.

What do you mean?
+Rep

 

[Bribe]

This is what I have so far. I will test it when I get home to see if it is working correctly (maybe I mixed up a variable or two), but then I will post the working on later tonight or tomorrow morning.

// Added udg_ in case you want to port this to plain JASS version, it's easy for you.

library IsPrime
globals
	private integer udg_integer
	private integer udg_testint
	private integer udg_stopint
	private boolean udg_boolean
endglobals

function IsPrimeEnum takes nothing returns nothing
	local integer i = udg_integer
	loop
		exitwhen i <= udg_stopint
		if ModuloInteger(udg_testint, i) == 0 then
			set udg_boolean == true
			return
		endif
		set i = i - 1
	endloop
endfunction

function IsPrime takes integer o returns boolean
	local integer i = o / 2 + 1
	if o == 2 then
		return true
	elseif o == 0 or o == 1 or ModuloInteger(o, 2) == 0 then
		return false
	elseif i < 0 then
		set i = -i
	endif
	set udg_testint = o
	set udg_boolean = false
	loop
		exitwhen i < 500
		set udg_stopint = i - 500
		set udg_integer = i
		call ExecuteFunc("IsPrimeEnum")
		if udg_boolean then
			return false
		endif
		set i = i - 500
	endloop
	set udg_integer = i
	set udg_stopint = 2
	call ExecuteFunc("IsPrimeEnum")
	return not udg_boolean
endfunction
endlibrary

 

[priest170234]

Haha, your code seems much complex

I don't get almost everything.. Thanks for trying to improve my code!

 

[Maker]

Try this:

function Trig_IsPrime_Conditions takes nothing returns boolean
    return SubString(GetEventPlayerChatString(), 0, 2) == "p "
endfunction

function Trig_IsPrime_Actions takes nothing returns boolean
    local boolean b = false
    local integer i = S2I( SubString(GetEventPlayerChatString(), 2 , StringLength( GetEventPlayerChatString() ) ) )
    local integer j
    
    if i == 2 or i == 3 then
        call BJDebugMsg("               " + I2S(i) + " is prime")
        return true
    else
        if ModuloReal( i , 2 ) == 0 then
            call BJDebugMsg("               " + I2S(i) + " is not prime")
            return false
        else
            set j = 3
            loop
                if ModuloReal( i , j ) == 0 then
                    call BJDebugMsg("               " + I2S(i) + " is not prime")
                    return false
                endif
                set j = j + 2
                exitwhen j * j > i
            endloop
        endif
    endif
    call BJDebugMsg("               " + I2S(i) + " is prime")
    return true
endfunction


function InitTrig_IsPrime takes nothing returns nothing
    set gg_trg_IsPrime = CreateTrigger(  )
    call TriggerRegisterPlayerChatEvent( gg_trg_IsPrime, Player(0), "p ", false )
    call TriggerAddCondition( gg_trg_IsPrime, Condition( function Trig_IsPrime_Conditions ) )
    call TriggerAddAction( gg_trg_IsPrime, function Trig_IsPrime_Actions )
endfunction

Type

p 1
p 666
p 10000000
etc.

 

[Bribe]

Maker, 10000000 will crash the thread

But yes, without multi-threading, that is the best way to do it. Although you want to use ModuloInteger, not ModuloReal (for efficiency)

 

[Maker]

Maker, 10000000 will crash the thread

Not for me. It works upto 2^31 - 1. I think WC3 doesn't support larger numbers than that.

But yes, without multi-threading, that is the best way to do it. Although you want to use ModuloInteger, not ModuloReal (for efficiency)

Dayum, why did I use ModuloReal? One of those retard moments I guess. Thanks for pointing that out.

 

[Bribe]

@Maker: It didn't crash the thread because it divides by 2 so I was wrong

Try putting in a super-high prime number, though. It will crash the thread.

 

[Berb]

How much memory exactly is allocated for an integer declaration?

 

[Nestharus]

This might help. It's more speedy than what many college professors write ; P, although it does hog up lots of memory to increase speed.

I wrote this for Sevion a long time ago for one of his assignments ; ). He beat his instructor : P.

This returns total divisors for a given number. You can rip it apart for primes.

This also doesn't hit op limit with large numbers as it uses trigger evaluations in the loop.

globals
    integer array primes
    boolean array primeNums
    integer primeCount = 0
    
    integer iteration = 0
    
    hashtable numberTable = InitHashtable()
    hashtable numberCount = InitHashtable()
    integer array divised
    hashtable divisorTable = InitHashtable()
endglobals

function GetDivisorCount takes integer i returns integer
    local integer curPrime = 0
    local integer divisors = 1
    local integer num = i
    local integer numl = 0
    local integer numc = 0
    local integer numlc
    local boolean add = false
    
    if (divised[i] != 0) then
        return divised[i]
    endif
    
    loop
        set iteration = iteration + 1
        if (i/primes[curPrime]*primes[curPrime] == i) then
            set i = i/primes[curPrime]
            if (primeNums[i]) then
                if (i != primes[curPrime]) then
                    set divised[num] = 4
                    call SaveInteger(numberTable, num, 0, i)
                    call SaveInteger(numberTable, num, 1, primes[curPrime])
                    call SaveInteger(numberCount, num, i, 2)
                    call SaveInteger(numberCount, num, primes[curPrime], 2)
                    return 4
                else
                    set divised[num] = 3
                    call SaveInteger(numberTable, num, 0, i)
                    call SaveInteger(numberCount, num, i, 3)
                endif
            else
                set numl = LoadInteger(numberCount, i, primes[curPrime])
                if (numl != 0) then
                    set numlc = numl+1
                    set divisors = divised[i]/numl*numlc
                else
                    set divisors = divised[i]*2
                    call SaveInteger(numberCount, num, primes[curPrime], 2)
                    set add = true
                endif
                set divised[num] = divisors
                set numc = 0
                loop
                    set iteration = iteration + 1
                    set numl = LoadInteger(numberTable, i, numc)
                    exitwhen numl == 0
                    call SaveInteger(numberTable, num, numc, numl)
                    if (numl == primes[curPrime]) then
                        call SaveInteger(numberCount, num, numl, numlc)
                    else
                        call SaveInteger(numberCount, num, numl, LoadInteger(numberCount, i, numl))
                    endif
                    set numc = numc + 1
                endloop
                if (add) then
                    call SaveInteger(numberTable, num, numc, primes[curPrime])
                endif
                return divisors
            endif
        else
            set curPrime = curPrime + 1
            if (curPrime == primeCount) then
                set primes[curPrime] = i
                set primeCount = primeCount + 1
                set primeNums[i] = true
                set divised[i] = 2
                return 2
            endif
        endif
    endloop
    return 0
endfunction

function GetNumber takes integer range returns integer
    local integer biggest = 0
    local integer count = 0
    local integer curDivisorCount = 0
    local integer i = 0
    
    if (not primeNums[2]) then
        set primes[0] = 2
        set primeNums[2] = true
        set primes[1] = 3
        set primeNums[3] = true
        set primeCount = 2
        set divised[1] = 1
        set divised[2] = 2
        set divised[3] = 2
    endif
    
    set i = 1
    loop
        set iteration = iteration + 1
        set curDivisorCount = GetDivisorCount.evaluate(i)
        if (curDivisorCount >= count) then
            set biggest = i
            set count = curDivisorCount
        endif
        set i = i + 1
        exitwhen i > range
    endloop
    
    call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 90000, "count: " + I2S(count))
    return biggest
endfunction

struct tester extends array
    private static method start takes nothing returns nothing
        call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 90000, "number: " + I2S(GetNumber(5000))+"\n-------------")
        call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 90000, "iteration: " + I2S(iteration))
        set iteration = 0
    endmethod
    
    private static method onInit takes nothing returns nothing
        call TimerStart(CreateTimer(), 1, false, function thistype.start)
    endmethod
endstruct

 

[priest170234]

Wow.. I got so much to learn
Code updated.
Can someone answer me this:
Why do it NOT return anything at large numbers (like 2^32-1). It seems the trigger had halt. But not WCIII Hang.
Then when I enter a value small (like 2), it tells me that 2^32-1 is not prime? Why doesn't it immediately tell me that it is not prime?

library CheckPrime
    globals 
        integer int                 // Constant (Dividend), does not change at ALL until checked = false
        integer int_2               // Updates (Divisor)
        boolean checked = false
        boolean isPrime
    endglobals

    function CheckPrime takes integer number returns boolean
        if(number<=1) then          // Integers Less than or Equal to 1 are NOT Prime
            call BJDebugMsg("Please enter a value larger than 1!")
            set isPrime = false
        else
            ////////////////////////////////////////////
            if(checked == false) then
                set checked = true
                set int = number
            endif
            ////////////////////////////////////////////
            set int_2 = number
        
            if (ModuloInteger(int, int_2) == 0) and (int != int_2) then // Divisible, and int not equal to int_2, NOT PRIME
                set int_2 = 0                                           // Immediately end this function.
            endif
        
            if (int_2 == 0) then        // If Its not a Prime Number
                call BJDebugMsg(I2S(int)+" is NOT Prime!") 
                set checked = false
                set isPrime = false
            else                        // Prime so far?
                if(int_2-1 == 1) then   // If the next number becomes 1, and so far it still prime, then the number IS PRIME!
                    call BJDebugMsg(I2S(int)+" IS Prime!") 
                    set checked = false
                    set isPrime = true
                else
                    set int_2 = int_2 - 1       // Not Prime? Continue checking the Divisor until it becomes 2.
                    call CheckPrime(int_2)      // Reccur the function.
                endif
            endif
        endif
        return isPrime
    endfunction
endlibrary

 

[Bribe]

It seems the trigger had halt. But not WCIII Hang.

This is why I have made a point to mention you need to split it into multiple threads, otherwise it will crash the thread. Splitting the workload into chunks via ExecuteFunc is the way I implemented.

 

[Nestharus]

I split it up by TriggerEvaluate, which is a bit faster than ExecuteFunc : P.

 private integer int                 // Constant (Dividend), does not change at ALL until checked = false
        private integer int_2               // Updates (Divisor)
        private boolean checked = false
        private boolean isPrime

Learn to use private

Didn't really read the code, but some, if not all, of those globals could probably be made into locals.

call CheckPrime(int_2) //should be your trigger evaluation. Return via a global and pass arg via a global

 

[Bribe]

ExecuteFunc creates a new thread, so does TriggerExecute, but TriggerEvaluate does not create a new thread and you will run into problems with high numbers

GetDivisorCount.evaluate(i)

Needs to be:

GetDivisorCount.execute(i)

 

[Nestharus]

Actually, you won't run into probs with large numbers. It still resets op limit for the evaluate...

my little snippet there worked with insanely large numbers. The only reason I didn't bother with larger is because the script took a long time to get all of the divisors. It never once stopped on me.

The op limit is op limit squared with trigger evaluate (op limit per evaluation and op limit on root).

 

[Bribe]

Evaluate resets the op limit? How do you learn stuff like this? That is important information, because Evaluate is a lot faster than Execute. Do you know if you get bonus operations per condition if you have multiple conditions attached to the same trigger? (does that make sense?)

 

[Nestharus]

You do... but you can only have so many things running at the same time. If you try to run triggers within triggers within triggers, and etc, I don't quite remember, but I think wc3 crashes. I performed those tests a long time ago >.<.

You learn stuff like this by making massive loops. I saw no dif between execute and evaluate besides speed.

I'm guessing evaluate and execute both run on new threads, but execute has some extra overhead for some reason?

 

[Bribe]

Execute lets you do TriggerSleepAction. Whee.