pennineacute Posted November 8, 2015 Share Posted November 8, 2015 I was writing a program to calculate whether a number was prime. It worked no issues and was quite fast.I then decided to enhance this, by calculating the factors of the number, if the number was not prime. This has dramatically slowed the program, for the following reason.Initialially I set is_it_prime to true, thereby assuming that the number was prime, until proven otherwiseI then ran a while loop with two conditions, one being is_it_prime being true. Once a number has been proven not to be prime, it is a waste to carry on testing.Now to get my factors working, I have had to remove this boolean condition. Was wondering if anyone could come up with any other ideas. </head> <body> <body style="background-color:grey"> <?php $number_to_test=$_POST["number"]; $factors=array(); $factorposition=0; $interim_testing_number=2; $is_it_prime=true; // Assume number is prime unless proven not to be $max_loop = sqrt($number_to_test); while ($interim_testing_number<=$max_loop) { if ($number_to_test % $interim_testing_number==0 ){ $is_it_prime=false; // Number is definately not prime as no remainder $factors[$factorposition]=$interim_testing_number; $factorposition++; if ($number_to_test/$interim_testing_number != $interim_testing_number) { $factors[$factorposition]=$number_to_test/$interim_testing_number; $factorposition++; } } $interim_testing_number++; } if ($is_it_prime && $number_to_test>1) { print "$number_to_test is PRIME"; } else { print "$number_to_test is NOT PRIME<br>"; sort($factors); if ($number_to_test > 1){ print "Its factor(s) are "; if ($factorposition-1>0){ for ($i=0;$i<$factorposition-1;$i++){ echo "$factors[$i], "; } echo "and ".$factors[$factorposition-1]; } else { echo $factors[0]; } } else { echo "Numbers less than 2 are not prime by default"; } } print "<br><br><br>"; ?> <a href="index.html"><img src="Images/ilovemaths.png" height=200 witdth=170 alt="Maths is Fun"/></a> </body> </html> Quote Link to comment Share on other sites More sharing options...
pennineacute Posted November 8, 2015 Author Share Posted November 8, 2015 Program is running herehttp://andylittlewood.co.uk Quote Link to comment Share on other sites More sharing options...
ginerjm Posted November 8, 2015 Share Posted November 8, 2015 Logic seems flawed. First - you only need to test half the value of the starting value - not the square root. Second - once you have determine that there is no remainder from your mod test, why do you continue on with that other logic? Quote Link to comment Share on other sites More sharing options...
pennineacute Posted November 8, 2015 Author Share Posted November 8, 2015 Re your first comment. Let's say testing to see if 100 is prime. You only have to check up to 10 which is the square rootEG, if 2 is a factor of 100, then so is 504 is a factor of 100, then so is 255 is a factor of 100, then so is 2010 is a factor of 100, which is a repeated factor, as 100/10 = 10That is why I only went up to the square root.re second.When I first wrote the program, I just wanted to see if a number was prime. Then I decided to enhance it, by showing the factors of a non-prime number. So using 100 as an example, after testing that division by 2 shows it is a non-prime number and therefore 2 and 50 are factors, I need to carry on testing, to get the remaining factors. Quote Link to comment Share on other sites More sharing options...
ginerjm Posted November 8, 2015 Share Posted November 8, 2015 Ok - lost sight of that - was still thinking about primes. Quote Link to comment Share on other sites More sharing options...
Zane Posted November 8, 2015 Share Posted November 8, 2015 FWIW, here's an interesting video on solving primes. It's a pretty straightforward formula. Seems like it's be a nice programming challenge as well. 1 Quote Link to comment Share on other sites More sharing options...
pennineacute Posted November 11, 2015 Author Share Posted November 11, 2015 Aprreciate that link, thanks Quote Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.