Home Tutorials Forums Articles Blogs Movies Library Employment Press

Go Back   ActionScript.org Forums > ActionScript Forums Group > ActionScript 3.0

Reply
 
Thread Tools Rate Thread Display Modes
Old 02-09-2010, 04:08 PM   #1
nikeman
Registered User
 
Join Date: Feb 2010
Posts: 7
Default Determine is a number is prime or not

Hey guys

I'm new at this forum, and I have a question related to a function I'm trying to make. It is supposed to tell me whether a number is prime or not. It works well up to pretty large numbers, but when i enter 10 digit-numbers, flash is telling me it's a prime number even when the last digit is 0.

One of my classmates have made a similar program, but he is not having the same problem as I am.
ActionScript Code:
// function primeNumber (tall:int):Boolean {     var count:uint = 2;     var i:uint = 0; //var used to define whether a number is prime or not     while (count<=Math.sqrt(tall)) {         if (tall%count == 0) {            i++; //if it's a prime number, i will never be more than 0. If it's not, i will be at least 1.         }         else {         i = i         }      count++;     }         if (i == 0) {     return true;     }     else {     return false;     } }    trace(primeNumber(8035154740)); //flash says true
Can you guys look into it and tell me what I am doing wrong?

Thanks

nikeman

Last edited by CyanBlue; 02-09-2010 at 04:55 PM. Reason: AS Tag applied...
nikeman is offline   Reply With Quote
Old 02-09-2010, 04:37 PM   #2
jordanmoore
Jordan Moore
 
Join Date: Aug 2009
Location: England
Posts: 76
Default

I haven't used your code in this example, but it seems to work on the number you had problems with.

ActionScript Code:
var num = 8035154740; var nums = Math.floor(Math.sqrt(num)); var i:Number = 1; var prime = " is"; while (++i <= nums) {     if ((num % i) == 0) {         prime = " is not";         i = nums;     } } trace(num + prime +" a prime number");

Or put into a function like your code:
ActionScript Code:
function primeNumber(num) {     var nums = Math.floor(Math.sqrt(num));     var i:Number = 1;     var prime = " is";     while (++i <= nums) {         if ((num % i) == 0) {             prime = " is not";             i = nums;         }     }     trace(num + prime +" a prime number"); } primeNumber(8035154740);


Please note that this is not 100% my work, I used someone else's javascript code and converted it to AS3.
I got the code from this site, so credit to the author.

Last edited by jordanmoore; 02-09-2010 at 05:00 PM. Reason: 2nd exampe and more detail.
jordanmoore is offline   Reply With Quote
Old 02-09-2010, 05:32 PM   #3
nikeman
Registered User
 
Join Date: Feb 2010
Posts: 7
Default

thank you!

However, in order for me to learn from my failures, I need someone to explain me what is wrong with my code. As far as i can see they are pretty similar.


EDIT: Seems changing the parameter in the head from
(tall:int):Boolean
to (tall:Number):Boolean did the trick. Why is that?
sincerely,

nikeman

Last edited by nikeman; 02-09-2010 at 05:38 PM. Reason: new info
nikeman is offline   Reply With Quote
Old 02-09-2010, 05:54 PM   #4
jordanmoore
Jordan Moore
 
Join Date: Aug 2009
Location: England
Posts: 76
Default

I'm not entirely sure why, but here is my thoughts.

'int' is short for 'integer', an integer refers to a whole value.
E.g the number 1 is an integer where as 1.7 is not.

If you are defining a variable as an int then you are saying it can only hold whole numbers and AS3 may be being 'clever' by rounding the values before storing them in the variable.

By using 'number' you are saying that the variable can hold any numeric value - including ones with decimal places, so in this case is can hold the 1.7 value because it IS a number.

The error may have happened because it is rounding the values before testing them, consequently you are testing a value other than the value you wish to test.

That is only my take on the error - but it seems logical to me.
jordanmoore is offline   Reply With Quote
Old 02-09-2010, 06:11 PM   #5
abeall
Senior Member
 
Join Date: Feb 2006
Location: Washington, DC
Posts: 2,796
Send a message via AIM to abeall
Default

I didn't read the whole thread but jordanmoore is right, when you type a variable as an int, all assignments to it will automatically get rounded down to the nearest integer without throwing an error:

ActionScript Code:
var i:int = 1.8423566; trace(i); // output "1"
__________________
Aaron Beall | Flash portfolio | Fireworks extensions | Twitter
abeall is offline   Reply With Quote
Old 02-09-2010, 06:33 PM   #6
nikeman
Registered User
 
Join Date: Feb 2010
Posts: 7
Default

Let me see if I got it right:

The large number i was having trouble with because flash reported it as a prime, was in fact an even number, and therefore also an integer. This is why i can't understand changing to tall:Number would make any difference.

When I enter a number to the function i give tall:int a value as only whole numbers can be prime numbers, which would mean I wouldn't input a non-integer. Therefore I decided to use int and not Number.

What I'm trying to say is that flash rounding the square root of the input down to the nearest non-integer wouldn't lead to the program making a mistake

Last edited by nikeman; 02-09-2010 at 06:36 PM. Reason: Rethink
nikeman is offline   Reply With Quote
Old 02-09-2010, 07:28 PM   #7
newblack
dondeEstanMisPantalones?
 
newblack's Avatar
 
Join Date: Nov 2005
Location: New York Proper
Posts: 1,355
Send a message via AIM to newblack
Default

the reason your original function is incorrectly specifying primeness is because the value you're assigning exceeds the amount that can be represented in 31 bits, so it's wrapping around and setting the int (when you call the function) to a negative value. You're taking the square root of this negative value, which evaluates to NaN because it's not a real number. Your conditional thus never evaluates to true.

one point is that your algorithm is inefficient. it continues to check for primeness even after it's proven otherwise. as soon as your tally of divisors exceeds 1, you should return false.
__________________
i am gibreel farishta
general relativity
jellytanks alpha redux
newblack is offline   Reply With Quote
Old 02-09-2010, 07:44 PM   #8
nikeman
Registered User
 
Join Date: Feb 2010
Posts: 7
Default

Interesting. Thanks!

Now why is it that this problem does not occur when I set the parameter to Number?
I'm sorry if this is a dumb question.

Speaking of the inefficiency I came to think of it like an hour ago, so I fixed my function to look like this:

Code:
while (count<=Math.floor(Math.sqrt(tall))) { 
		if (tall%count == 0) { 		
		i++
		count = tall; //this is the change
		}
		else { 
		count++;
	}
}
What I find strange is that when I enter a 20 digit number that ends with 0, 2, 4, 6 or 8 it doesn't report false instantly. Instead it keeps going and times out (15 sec rule). This is weird seeing the first number it would check is 2, and since the 20 digit number ended with an even number, the result of the modulo should be 0.

I also came to think of that it's useless checking any multiplies of the number already checked (if, say 2, doesn't add up in the input, then 12 won't do it either). The most efficient method would be to only check if the input is dividable by primes smaller or equal to the square root of the input number. However, I have no idea how to convert that to AC-code

Last edited by nikeman; 02-09-2010 at 08:00 PM. Reason: changed vars to correspond with the first example
nikeman is offline   Reply With Quote
Old 02-09-2010, 08:09 PM   #9
newblack
dondeEstanMisPantalones?
 
newblack's Avatar
 
Join Date: Nov 2005
Location: New York Proper
Posts: 1,355
Send a message via AIM to newblack
Default

Numbers are 64-bit double precision, so they can store higher values than int. the algorithm is simple:
ActionScript Code:
function isPrime( candidate:Number ) : Boolean {     var sqrtCandidate:Number = Math.round( Math.sqrt( candidate ) );     for( var i:int = 2; i < sqrtCandidate; i++ )     {         if( candidate % i == 0 ) return false;     }     return true; }
__________________
i am gibreel farishta
general relativity
jellytanks alpha redux
newblack is offline   Reply With Quote
Old 02-09-2010, 10:12 PM   #10
lordofduct
Senior Member
 
lordofduct's Avatar
 
Join Date: Feb 2008
Location: West Palm Beach, FL
Posts: 3,872
Default

check out this class:

http://code.google.com/p/lodgamebox/...til/LoDMath.as

all the way near the bottom:

ActionScript Code:
/**                  * Check if a value is prime.                  *                  * @param val - uint to check for primality                  *                  * In this method to increase speed we first check if the value is <= 1, because values <= 1 are not prime by definition.                  * Then we check if the value is even but not equal to 2. If so the value is most certainly not prime.                  * Lastly we loop through all odd divisors. No point in checking 1 or even divisors, because if it were divisible by an even                  * number it would be divisible by 2. If any divisor existed when i > value / i then its compliment would have already                  * been located. And lastly the loop will never reach i == val because i will never be > sqrt(val).                  *                  * proof of validity for algorithm:                  *                  * all trivial values are thrown out immediately by checking if even or less then 2                  *                  * all remaining possibilities MUST be odd, an odd is resolved as the multiplication of 2 odd values only. (even * any value == even)                  *                  * in resolution a * b = val, a = val / b. As every compliment a for b, b and a can be swapped resulting in b being <= a. If a compliment for b                  * exists then that compliment would have already occured (as it is odd) in the swapped addition at the even split.                  *                  * Example...                  *                  * 16                  * 1 * 16                  * 2 * 8                  * 4 * 4                  * 8 * 2                  * 16 * 1                  *                  * checks for 1, 2, and 4 would have already checked the validity of 8 and 16.                  *                  * Thusly we would only have to loop as long as i <= val / i. Once we've reached the middle compliment, all subsequent factors have been resolved.                  *                  * This shrinks the number of loops for odd values from [ floor(val / 2) - 1 ] down to [ ceil(sqrt(val) / 2) - 1 ]                  *                  * example, if we checked EVERY odd number for the validity of the prime 7927, we'd loop 3962 times                  *                  * but by this algorithm we loop only 43 times. Significant improvement!                  */                 static public function isPrime( val:int ):Boolean                 {                         //check if value is in prime number range                         if (val < 2) return false;                                                 //check if even, but not equal to 2                         if (!(val % 2) && val != 2) return false;                                                 //if 2 or odd, check if any nontrivial divisor exists                         for (var i:int = 3; i <= val / i; i += 2)                         {                                 if (!(val % i)) return false;                         }                                                 return true;                 }

as you can tell I also outline the analytical proof for my algorithm


there may be other functions you might find useful:

factorsOf(...)
factorial(...)
gammeFunction(...)
fallingFactorial(...)
risingFactorial(...)
binCoef(...)
risingBinCof(...)

there was an older version of my primality algorithm that technically should be more efficient then the current... but because Flash likes loops more then some other things, using binomial coefficients turned out slower.


@newblack - not to be rude, but I'd like to point out an issue with using Number (double floating point value), due to the significant value range being much smaller then the MAX value, you can get false positives sometimes for very large primes.

Personally I used integer only because I figured if you really needed to know the primality of very large values (greater then 2^31 - 1), then you probably don't want to use flash to decide it considering that by our algorithm (we essentially use the same algorithm) you'd potentially loop 23170+ times. (more so if you used your specific algorithm)

[ ceil(sqrt(2147483647) / 2) - 1 ] == 23170
__________________
www.lordofduct.com - come read my blog!

If you want to know how to program, take a math class, take a lot of math classes!

Last edited by lordofduct; 02-09-2010 at 10:34 PM.
lordofduct is offline   Reply With Quote
Reply


Thread Tools
Display Modes Rate This Thread
Rate This Thread:

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT. The time now is 11:29 PM.

///
Follow actionscriptorg on Twitter

 


Powered by vBulletin® Version 3.8.5
Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.
Ad Management plugin by RedTyger
Copyright 2000-2013 ActionScript.org. All Rights Reserved.
Your use of this site is subject to our Privacy Policy and Terms of Use.