What is an appropriate measure of the size of the problem depends on the problem.

CB

Printable View

- Apr 20th 2010, 12:58 AMCaptainBlack
- Apr 20th 2010, 01:43 AMundefined
I like how there are a couple conversations going on at once here, heh.

I copied and pasted your code for use with my XAMPP setup and got problems with 2702811*sometimes*but not always, and I wasn't able to get an error with 15999.

To tell the truth, I don't understand the logic of your code, but I notice that the two functions call each other an awful lot.

It seems like you're not doing anything more complex than trial division, so what do you think of this instead?

[php]

<?php

$num = 342132;

if ($num < 2) {

echo "No prime factors.";

exit;

}

echo "The prime factorization of " . $num . " is:<br />";

while ($num % 2 == 0) {

echo "2<br />";

$num /= 2;

}

while ($num % 3 == 0) {

echo "3<br />";

$num /= 3;

}

$lim = floor(sqrt($num));

for ($i = 5, $inc = 2; $i <= $lim; $i += $inc, $inc = 6 - $inc) {

if ($num % $i == 0) {

echo $i . "<br />";

$num /= $i;

while ($num % $i == 0) {

echo $i . "<br />";

$num /= $i;

}

$lim = floor(sqrt($num));

}

}

if ($num != 1) echo $num;

?>

[/php]

Note: I introduce $inc in order to avoid numbers congruent to 0 (mod 3). - Apr 20th 2010, 02:12 AMCaptainBlack
Consider semi-primes of the form $\displaystyle n=2 \times p$ or $\displaystyle n=3 \times p$ where $\displaystyle p$ is a prime greater than $\displaystyle 5$.

Note that $\displaystyle p>\sqrt{n}$ which looks like it will crash your algorithm.

I would guess that $\displaystyle 31998$ may also give this problems.

I would conjectute that any number of the form $\displaystyle 2^n3^mp$ where $\displaystyle p>2^n3^m$ is a prime will give problems (this is a conjecture because I cant be bothered to analyse such horrible code in detail)

CB - Apr 20th 2010, 02:21 AMundefined
Suppose n = 14, then the program will first divide out all the 2's, so that $lim = floor(sqrt(7)) = 2. The program will effectively skip the main loop and then correctly conclude that 7 is prime and print it as one of the factors.

Edit: This stuff was added afterwards

31998 worked fine. If my code is so horrible, let's see yours.

Oh and for the conjecture, $\displaystyle 745848 = 2^3*3^4*1151$ works just fine as well. - Apr 20th 2010, 02:29 AMCaptainBlack
The horror of the code may be a result of using watever language that is in, or it may be the result of a poorly thought out algorithm I can't tell.

If you had an algorithm spec in a more comprehensible language or psuedo-code I would have more confidence in it being the language rather than the algorithm.

CB - Apr 20th 2010, 02:49 AMundefined
Fair enough, although PHP is quite common. Here's Java:

Code:`public ArrayList<Integer> naiveFactorise(int n) {`

// returns prime factors in ascending order, duplicates allowed

ArrayList<Integer> pFacts = new ArrayList<Integer>();

if (n < 2) return pFacts;

while (n % 2 == 0) {

pFacts.add(2);

n /= 2;

}

while (n % 3 == 0) {

pFacts.add(3);

n /= 3;

}

int lim = (int)Math.sqrt(n);

for (int i = 5, inc = 2; i <= lim; i += inc, inc = 6 - inc) {

if (n % i == 0) {

pFacts.add(i);

n /= i;

while (n % i == 0) {

pFacts.add(i);

n /= i;

}

lim = (int)Math.sqrt(n);

}

}

if (n != 1) pFacts.add(n);

return pFacts;

}

Edit: For clarification, from my first post I've been writing about a program to produce the prime factorization of n using trial division. Although the OP said the original goal was merely to decide prime vs. composite, the functionality of the program posted by the OP was to produce all the prime factors with multiplicity, so that's what I went by. Obviously the decision problem is easier and simpler. This might have contributed to my code seeming "horrible." - Apr 20th 2010, 02:54 AMCaptainBlack
Unless you are dealling with very large numbers or speed is of the essense keep it simple:

Code:`function IsPrm(num)`

//

// psuedo-code for crude primallity testing

//

// assumption: num is an integer type

//

if (num<=1)

return false

end

if (num==2)

return true

elseif (mod(num,2)==0)

return false

end

for idx=3 to floor(sqrt(num)) step 2

if mod(num,idx)==0

return false

end

end

return true

endfunction

CB - Apr 20th 2010, 10:46 AMsuperdude
I realize that both my logic and style where very poor for this program. I have written a much more elegant prime factoring program and if you like I can post it. Efficiency is not an issue, if it was I'd use this. My question that I'm asking is why do certain numbers crash the program?

- Apr 20th 2010, 11:04 AMundefined
I don't have a definitive answer (debugging your code slows down my system so it's a bit of a pain), but your two functions call each other a huge number of times in general, so maybe there is a situation where a stop condition is accidentally skipped and you are left with infinite recursion. If I were you I would introduce global variables to keep track of function calls, and periodically print out the values of the key variables, either as soon as the function is called, or within the loops, or both, to try to catch runaway recursion. In the process you might spot an issue such as integer overflow, if such a problem exists. And of course, infinite recursion is essentially the same as an infinite loop, which might be the culprit.

- Apr 20th 2010, 11:07 AMsuperdude
- Apr 20th 2010, 11:20 AMundefined
Then perhaps the error lies somewhere outside the block of code you posted, because I ran it as-is and never got that problem.

I find it extremely unlikely that my version of PHP would behave that much differently from yours and that it's a bug with the PHP interpreter, although I suppose it can't be ruled out entirely without further testing. - Apr 20th 2010, 11:25 AMsuperdude
This is my new version. I'm looking for criticism:

[PHP]

<?php

$num = 15999;

if($num%2 != 0 && $num%3 != 0 && isPrime($num))

{

print($num.' is prime');

exit;

}

print('The primefactorization of '.$num.' is:<br />');

checkSmallPrimes($num, 2);//factors out 2s

checkSmallPrimes($num, 3);//factors out 3s

for($i = 5; $i <= floor(sqrt($num)); $i += 2)

{

if(isPrime($i))

{

while($num%$i==0)//having this as a while loop instead of if increases efficency

{

$num = $num/$i;

print($i.'<br />');

}

if(isPrime($num))

{

print($num);

exit;

}

}

}

/*returns true if agrument is prime greater than 3, otherwise returns false*/

function isPrime($maybePrime)

{

for($j = 3; $j <= floor(sqrt($maybePrime)); $j += 2)

if($maybePrime%$j == 0)

return false;

return true;

}

//$num is being passed by reference

function checkSmallPrimes(&$num, $smallPrime)

{

while($num%$smallPrime==0)

{

$num /= $smallPrime;

print($smallPrime.'<br />');

}

}

?>[/PHP] - Apr 20th 2010, 11:27 AMsuperdude
- Apr 20th 2010, 12:15 PMundefined
Sorry, I missed that part. I've never had to debug a language interpreter before, and I don't intend to replace my current PHP with one that is potentially buggy, so I guess I won't be of much help on that.

A small consistency issue: It seems that the program says "$num is prime" when $num is prime and > 3, but if $num == 2 or $num == 3, it will output its prime factorization rather than telling you it's prime.

I don't understand why you treat 3 as a special case; you could just start your loops at 3 instead of 5. The reason I treated 3 as special was because my increment scheme avoided multiples of 3 other than 3, thus I checked the numbers 2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, ... where the differences between two successive terms are 2 and 4 alternating, but starting with 5. This is just an optimization.

Also, I'm not sure if this is a real optimization or not, but I tend to pre-calculate the loop limit floor(sqrt($blah)) as another variable to prevent re-calculating the same thing many times -- possibly a given compiler/interpreter would do this anyway, depends on how smart it is I guess.

There's another inefficiency I noticed: you call isPrime() from within the main for() loop (the one that's not contained in a function), and you start trial division over at 5, but in reality it's impossible to have factors between 5 and $i of the main loop because you've divided them out already.

Also, you only call checkSmallPrimes() twice, but the while() loop inside your main for() loop has identical code. If you're going to encapsulate that code as a function, you might as well just call checkSmallPrimes() each time, possibly renaming it to reflect what it does more closely.

One final optimization I can see is that, for composite $num, at the beginning you call isPrime() and trial divide by 2 and all odd numbers up to sqrt($num), and then you do the exact same thing (starting at 5) in the main for() loop. It would be more efficient to keep a boolean value for primality, starting it at true and then setting it to false as soon as a factor < $num is found, thus combining the two loops into one.

One last very small point is that using the variable name $maybePrime inside a function called isPrime() seems redundant to me.

Hope you don't mind my tearing apart your code... it's all meant constructively. - Apr 21st 2010, 11:03 AMsuperdude
You have some valuable suggestions. Can you elaborate on how your increment scheme avoids multiples of 3 and how you know you won't miss any primes in between? So how do you know alternating between adding 2 and 4 skips multiples of 3? I'm busy today so I'll consider your suggestions in more depth and post back in a day or two.