02092010, 04:08 PM

#1

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 digitnumbers, 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; 02092010 at 04:55 PM.
Reason: AS Tag applied...



02092010, 04:37 PM

#2

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; 02092010 at 05:00 PM.
Reason: 2nd exampe and more detail.



02092010, 05:32 PM

#3

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; 02092010 at 05:38 PM.
Reason: new info



02092010, 05:54 PM

#4

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.



02092010, 06:11 PM

#5

Senior Member
Join Date: Feb 2006
Location: Washington, DC
Posts: 2,796

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"



02092010, 06:33 PM

#6

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 noninteger. 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 noninteger wouldn't lead to the program making a mistake
Last edited by nikeman; 02092010 at 06:36 PM.
Reason: Rethink



02092010, 07:28 PM

#7

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.



02092010, 07:44 PM

#8

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 ACcode
Last edited by nikeman; 02092010 at 08:00 PM.
Reason: changed vars to correspond with the first example



02092010, 08:09 PM

#9

dondeEstanMisPantalones?
Join Date: Nov 2005
Location: New York Proper
Posts: 1,355

Numbers are 64bit 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;
}



02092010, 10:12 PM

#10

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; 02092010 at 10:34 PM.



Thread Tools 

Display Modes 
Rate This Thread 
Linear Mode


Posting Rules

You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is Off



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

