Home Tutorials Forums Articles Blogs Movies Library Employment Press

 ActionScript.org Forums Determine is a number is prime or not
 Register FAQ Members List Social Groups Calendar Search Today's Posts Mark Forums Read

 02-09-2010, 04:08 PM #1 nikeman Registered User   Join Date: Feb 2010 Posts: 7 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...
 02-09-2010, 04:37 PM #2 jordanmoore Jordan Moore   Join Date: Aug 2009 Location: England Posts: 76 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.
 02-09-2010, 05:32 PM #3 nikeman Registered User   Join Date: Feb 2010 Posts: 7 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
 02-09-2010, 05:54 PM #4 jordanmoore Jordan Moore   Join Date: Aug 2009 Location: England Posts: 76 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.
 02-09-2010, 06:11 PM #5 abeall Senior Member   Join Date: Feb 2006 Location: Washington, DC Posts: 2,812 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
 02-09-2010, 06:33 PM #6 nikeman Registered User   Join Date: Feb 2010 Posts: 7 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
 02-09-2010, 07:28 PM #7 newblack dondeEstanMisPantalones?     Join Date: Nov 2005 Location: New York Proper Posts: 1,355 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
 02-09-2010, 07:44 PM #8 nikeman Registered User   Join Date: Feb 2010 Posts: 7 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
 02-09-2010, 08:09 PM #9 newblack dondeEstanMisPantalones?     Join Date: Nov 2005 Location: New York Proper Posts: 1,355 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
 02-09-2010, 10:12 PM #10 lordofduct Senior Member     Join Date: Feb 2008 Location: West Palm Beach, FL Posts: 3,872 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.

 Thread Tools Display Modes Rate This Thread Linear Mode Rate This Thread: 5 : Excellent 4 : Good 3 : Average 2 : Bad 1 : Terrible

 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 Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home ActionScript Forums Group     ActionScript 3.0     ActionScript 2.0     ActionScript 1.0 (and below)     Simple Stuff (Newbies) Flash General Questions     Flash 10 General Questions     Flash 9 General Questions     Flash 8 General Questions     Other Flash General Questions Flex     Flex 2, 3 & 4     Flex 1 Extensions and Plugins     Components     JSFL - Extending Flash Desktop, Mobile and non-browser Environments     AIR (Apollo)     FlashLite / Portable Devices Development     Projectors and CDs Supporting Technologies     HTML and JavaScript     haXe     Server-Side Scripting     Flash Remoting     Flash Media Server General     Best Practices     Gaming and Game Development     Animation and Effects     Flashants Support Forum Community Boards     General Chat     Just for Kicks Challenges     Detention Flash In Action     Site Check     Cool Sites     Widgets Decommissioned     Projects and Positions CMS Forums     Announcements Board     Content Postings / Updates     Product Review Requests     CMS Technical Questions     Process Questions     Collaboration & Suggested Articles

All times are GMT. The time now is 05:24 AM.

///