Jump to content

Prime Number Checking Function


chibineku
 Share

Recommended Posts

I'm writing a function to determine if a number is prime. It's been done before, but I am doing little code puzzles to solve problems with code, so it's cheating even asking for help.Here is what I have so far:

function isprime($val) {for($i=1; $i <= $var; $i++) {  if($var%$i==0 && $i!=1 && $i!=$var) {   return false;   break;  } else if($i == $var) {   return true;  }}}

It always returns not prime.My though process was:

  • for each number less than or equal to $var (the number in question)
  • check if the number is a factor, and if it is not equal to 1 or $var
  • if so, then the number is not prime
  • else if we reach $var without finding another factor, the number is prime

What am I doing wrong/not doing?

Link to comment
Share on other sites

Variable naming issues!By the way, you only have to test up to the square root of the number in question.

Link to comment
Share on other sites

This won't solve your problem, which I imagine is solved by now, but you can still simplify your logic.You do not need a break statement after a return statement. The function has already terminated so break never gets executed.You also do not need to test if $i == $val. 1., it is inefficient for every iteration of the loop to test for a condition that will be true only at the end of the cycle. If your number is very large, or you need to execute the function thousands of times, this test will slow you down. 2, When the loop is complete, $i does == $val. So the test is redundant as well. Eliminate the else block and simply return true immediately after the loop. As in:

for (blah) {   if (blah blah) {	  return false;   }}return true;

Edited by Deirdre's Dad
Link to comment
Share on other sites

Been there, done that! years ago i did in javascript, if you want js code to slow a server to standstill, this is the one to use.then i produced c++ program which provided prime numbers up to 999999 maybe larger, stored the results in text file, and used it in php file to show results from users selection.EDIT: OK not server to standstill, before you lot start correcting me

Edited by dsonesuk
Link to comment
Share on other sites

If you really want to optimise it, then you could use something like the Sieve of Eratosthenes to generate a list of low-magnitude prime numbers, and then while in the pre-calculated interval only test for division by those primes.

Link to comment
Share on other sites

If you really want to optimise it, then you could use something like the Sieve of Eratosthenes to generate a list of low-magnitude prime numbers, and then while in the pre-calculated interval only test for division by those primes.
How would you code something like that? I can't seem to wrap my mind around what it is you're trying to say. To code something like the Sieve of Eratosthenes doesn't seem very efficient to me. Wouldn't that be a lot of excess looping through arrays?
Link to comment
Share on other sites

How would you code something like that? I can't seem to wrap my mind around what it is you're trying to say. To code something like the Sieve of Eratosthenes doesn't seem very efficient to me. Wouldn't that be a lot of excess looping through arrays?
No, because you only go over (directly) to scratch the numbers you know for sure are NOT prime numbers. But yes, you'll have to traverse the whole array at least once, in order to check if a number is considered in the list or not. In the case of PHP, that's less of a hassle, because you can dynamically remove array elements while going over them. In other languages, doing the same would involve using hash tables (e.g. map) for achieving the same things, but with a limited benefit, mind you.
Link to comment
Share on other sites

Variable naming issues!By the way, you only have to test up to the square root of the number in question.
I am going to get my mantra tattooed into my arm: "If it doesn't work, READ IT!" Ty, Synook :) The Sieve is a cool algorithm, but more complex than my (now working) function. I am not sure why I only need to test up to the square root of the number, though?Deirdre's Dad: I thought as much (regarding the break and no else-if), but when I started having problems I wanted to be as explicit as possible to make sure there weren't any syntactical errors that wouldn't cause runtime errors but which would make the execution fail.Anyway, this was only part of the question, so I am going to go finish it now :)
Link to comment
Share on other sites

I am not sure why I only need to test up to the square root of the number, though?
Take the number 64 for example. The square root is 8, correct? But it is divisible by 2 and 4. 64/2 = 3264/4 = 16The next number it is divisible by is 8 so64/8 = 8There won't be any numbers greater than 8 we haven't already covered.
Link to comment
Share on other sites

Ah, I see, ty jkloth :)

Link to comment
Share on other sites

j00 guyz iz gotsta b kidding me, no? O.o :)

Link to comment
Share on other sites

j00 guyz iz gotsta b kidding me, no? O.o :)
When I was younger I was big into chat rooms so I knew all that internet lingo and txt speak stuff. But then I quit going into chat rooms and talking on im's so I forgot most of it plus all the new shtuff that kids these days are inventing. :)
Link to comment
Share on other sites

Btw, while we're on the subject of incomprehensible things, what on earth does your sig mean, jkloth?!

Link to comment
Share on other sites

Btw, while we're on the subject of incomprehensible things, what on earth does your sig mean, jkloth?!
U like?It's a saying my pa used to say. To be honest, I really don't know what it means either (if it means anything :) ). I'll leave it up to your imagination. :) Edited by jkloth
Link to comment
Share on other sites

How would you code something like that? I can't seem to wrap my mind around what it is you're trying to say. To code something like the Sieve of Eratosthenes doesn't seem very efficient to me. Wouldn't that be a lot of excess looping through arrays?
Besides what Deidre's Dad mentioned, you can also hard-code (or at least pre-calculate) the Sieve, so even if you need to check a thousand different numbers you only have to run the sieve algorithm once. Bear in mind also that if you calculate the Sieve up to just 113, then you can check numbers up to 12769 (133^2) without any additional calculations, and by that, the advantage is proportional to the square of the number of primes you calculate using the Sieve.
Link to comment
Share on other sites

Besides what Deidre's Dad mentioned, you can also hard-code (or at least pre-calculate) the Sieve, so even if you need to check a thousand different numbers you only have to run the sieve algorithm once. Bear in mind also that if you calculate the Sieve up to just 113, then you can check numbers up to 12769 (133^2) without any additional calculations, and by that, the advantage is proportional to the square of the number of primes you calculate using the Sieve.
Well, this has piqued my curiosity, so I wrote a function to simulate the Sieve. It works beautifully. So if I understand what your saying, I would just check if number $n is divisible by the list of primes I get from the Sieve? So this would only be more efficient if I needed to check a whole bunch of numbers and not just one at a time. Correct?
Link to comment
Share on other sites

Well, you have to see whether the Sieve is quicker than the straight division-test method. If it is faster, then using it would be more time-efficient in all cases. However if it was actually faster to test all divisors, but the Sieve was faster calculating the list of primes up to a certain number, the it would only be more optimal if you cached the resulting list. However, if the Sieve method (or your implementation of it) was so slow that even for sequences of primes it didn't beat checking every number using outright division, then it wouldn't be useful for any cases. Benchmark!

Link to comment
Share on other sites

Well, you have to see whether the Sieve is quicker than the straight division-test method. If it is faster, then using it would be more time-efficient in all cases. However if it was actually faster to test all divisors, but the Sieve was faster calculating the list of primes up to a certain number, the it would only be more optimal if you cached the resulting list. However, if the Sieve method (or your implementation of it) was so slow that even for sequences of primes it didn't beat checking every number using outright division, then it wouldn't be useful for any cases. Benchmark!
Hmm...I did a couple tests and my implementation (not surprisingly) turned out to be really slow. :) I'm far from an expert on optimization of code, so I expected that. :) Oh well, this was just an experiment.
Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...