Jump to content

Prime Numbers


pennineacute

Recommended Posts

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 otherwise

I 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>
Link to comment
Share on other sites

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 root

EG, if 2 is a factor of 100, then so is 50
4 is a factor of 100, then so is 25
5 is a factor of 100, then so is 20
10 is a factor of 100, which is a repeated factor, as 100/10 = 10

That 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.

 

Link to comment
Share on other sites

This thread is more than a year old. Please don't revive it unless you have something important to add.

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.