Problem with c# code that checkes if a number is prime

 private bool isPrime(int num)
      {
         if (num == 0 || num == 1)
            return false;     

         for (int j = 2;  j < num;  j++)
         {
            if (num % j == 0) return false;
         }else{
              for (int i= 2;  j < Math.Sqrt(num);  i++)
                   if (num % j == 0) return false;
        }

         return true;
      }

Select allOpen in new window

Would this help?

I see what all the numbers have in common. Their square roots are whole numbers, not fractional numbers. Once I figured that, I was able to fix the glitch like this:

         if (num == 0 || num == 1)
            return false;

         int num2 = (num % Math.Sqrt(num) == 0) ? (num - 1) : num;

         for (int i = 2; i < num2; i++)
            if (num % i == 0) return false;

         return true;

Thanks for your help.

Clarification:

What they all have in common is that their their roots are whole numbers **AND** their square roots are odd numbers.

But the point of sqrt is to improve performance. With your revised program, num2 is still num or close to it. If num2 is a large number, say, around a billion, wouldn't it be a lot faster to use something like sqrt(num).

Away from programming for a moment, think of the math. Your original use of sqrt got the right answer most of the time. Do you understand why it worked most of the time?

As it stands, your program is not taking advantage of the performance gained by using sqrt. Your instructor will not accept it.

>> their square roots are whole numbers
right - which means that those numbers are perfect squares.
3599 - not a perfect square (surprised that was on your list)

Also, since your found out that the number is a perfect square, then is that number a prime?

btw - I always thought 2 was a prime.

Here's the more correct answer.

       int num2 = (num % Math.Sqrt(num) == 0) ? (int)(Math.Sqrt(num) + 1) : (int)(Math.Sqrt(num));

         for (int i = 2; i < num2; i++)          
            if (num % i == 0) return false;

Before you subtracted one, and now you add one. What is the reasoning for the switch? When you subtracted one, you said your program worked. How about now?

Also, can you think of a way to remove that ternary altogether?

And did you figure out why using sqrt can give you the right answers?

Yeah you're right. I need to work on this some more.

ok, try to think more about the questions I asked. You are on the right track and close to a solution. Talk to you tomorrow.

Here are the answers I came up with  to your questions. If you remove 3599 and 5183 from my list (the original code actually works correctly on them), all the numbers in the list are perfect squares and divisible only by their square root, making them NOT prime. My original usage of Math.sqrt() worked most of the time because this situation is rare. This situation created a problem in the code for(int i = 0; i <Math.Sqrt(num); i++) because the loop never tested if my glitch numbers were  divisible by their square root. For example, in the case of num = 49, the loop never reached the iteration  i = 7 because  i  < Math.Sqrt(num)  became  7 < 7, which is false. So it never tested (49 % 7 == 0).
 
To correct the glitches, I used this ternary operator.

double num2 = (num % Math.Sqrt(num) == 0) ? (Math.Sqrt(num) + 1) : (Math.Sqrt(num));
for (int i = 2; i <= num2; i++)
  {
  }

The (Math.Sqrt(num) + 1) in the ternary corrects the problem for perfect squares. For example, for num = 49, it changes the false condition (7 < 7) to the true condition (7 < 8), thus ensuring that (49 % 7 == 0) is tested.

As for how to remove the ternary altogether, I can just change the condition i < Math.Sqrt(num) in the original code to i <= Math.Sqrt(num). Below is my final version that seems to work 100% of the time.

      public static bool IsPrime(int num)
      {
         if (num == 0 || num == 1)
            return false;
         
         for (int i = 2; i <= Math.Sqrt(num); i++)        
            if (num % i == 0) return false;        

         return true;
      }

Sounds like a reasonable argument for the change you made.
Now the <= test is sometimes slower than a < test. Can you think of a simple way to use the < operator?

Don't forget that i is an int. Do you know what happens in your test w.r.t. i?

In the test i <= Math.Sqrt(num), I think Math.Sqrt(num) gets converted from a double to an int because i is an int. Is that what happens?

Is this the simple way to use < that you're referring to?
i < Math.Sqrt(num) + 1

If so, I'll change i <= Math.Sqrt(num) to i < Math.Sqrt(num) + 1.

>> In the test i <= Math.Sqrt(num), I think Math.Sqrt(num) gets converted from a double to an int because i is an int. Is that what happens?

No, promotion goes from smaller type to larger type. If sqrt were demoted to an int, there would be data loss. And the compiler doesn't want to do that automatically (although the programmer may choose to do so if it makes sense).

>> i < Math.Sqrt(num) + 1
Yes, but beware of the floating point when you are just counting. Floating operations usually take longer than integer operations.
Give it a try and see whether you get the correct results.

Question. For num's around 1,000,000, how much faster do you think your program goes for num's that are prime?

If those numbers are prime, it probably cuts the execution time in half. That's my guess.

Is "half" the relationship between 1000000 and Math.Sqrt(1000000)?

I meant half the number of processor clock cycles to run the program to completion.

So what limits the number of processor clock cycles to run the program to completion?

I think I misunderstood phoffric's question. This is what I initially thought he meant: suppose you have Array1 and Array2. Array1 contains all integers between 1 and 100000. Array2 contains only the prime numbers between 1 and 100000. It would take half the number of clock cycles to iterate through Array2 than it would for Array1.

But now I think this is what phoffric meant: suppose num is some integer >= 1000000. How much faster will it take to execute (int j = 0; j < num; j++) than to execute for(int j = 0; j < Math.Sqrt(num); j++)?  I'm guessing the j < Math.Sqrt(num) version will execute in half the number of clock cycles as the j < num version.

Suppose some num is a prime integer around 1 million. Without using sqrt, you looped through the body about 1 million times. Then you included the sqrt in the test to stop the loop. What is the sqrt of 1,000,000?

Why does using sqrt even work? Why doesn't it get the wrong answer since it is not checking all cases up to around 1 million?

Because if num is divisible by some integer(s), then the square root of num will also be divisible by some integer(s). So we only have to test the integers less than the square root of num.

Let me rephrase that...

If num is divisible by an integer that is greater than the square root of num, then num must also be divisible by an integer that is less than the square root of num. If you multiply the two integers, you get num. We're just looking for the integer that's less than the square root of num. We don't need to find the other integer that's greater than the square root of num.

My friend, Scott, and I wrote a program to find prime numbers that ran on a Monroe Calculator back in the seventies while in college. Because of the limited processing power, we had to make the program as efficient as possible, Here are the steps we used to optimize the algorithm for finding out if num is a prime number.
1. Only check whole numbers greater than 1.
2. Loop through all integers from 2 to j-1 and test for divisibility. Make sure the loop pretests the range before the divisibility or 2 will not be found as prime.
3. OPTIMIZATION #1: As many pointed out above, you only need to test up to the square root of num. Since you do need to check the actual square root it needs to be a "less then" or "equal to" check. Because of rounding and type conversion, to be safe you should add 1 to the square root of num. (sqrt(9) may actually compute as 2.999999 and truncate when converting to int as 2.) How much does this speed up the algorithm? For num = 101, instead of checking 2 -100, or 99 factors, you only check 2 - 11 or 10 factors. That's about 10 times faster. For 10,001, it is only 100 instead of 9,999 or about 100 times faster. So the savings is of a magnitude equal to the square root of the number being tested. We were testing numbers with many more digits, so this cut the run time from years to days.
OPTIMIZATION 2: Store the (square root of num) + 1 in a integer variable. The repeated computation of the square root and conversion to int took much longer than the divisibility test itself.
OPTIMIZATION 3: Once you check divisibility by 2, you know that num is not even, so you can skip all even divisors. So change your loop increment from j++ to j = j+2 and start at 3 after you check the 2. This cuts run time in half.
OPTIMIZATION 4: Just like #3, once you check 3 you don't need to check multiples of three, like 6, 12, 15, etc. This proved quite interesting on how to figure which factors to check. If we eliminate factors that have 2 and 3, we are left with: 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35 ... Looking at the differences between these factors, they are 2, 4, 2, 4, 2, 4. So starting at 5 (after checking 2 and 3) we add 2 then 4, then 2 then 4, ... You can easily handle this in an array. You can continue to eliminate multiples of more factors (which will be primes themselves) and you will find similar patterns, just longer. We eliminated all factors up to 1000 (if I remember correctly). We programmed it to test the first factors and created the array to use beyond that. Eliminating factors of three eliminates 1/3 of the tests, 5 eliminates another 1/5.

I leave it up to others to develop the actual code. My friend and I did it in machine language and had to develop our own % function. With the array of numbers to add to get the next factor to test, we found we could "fold" the sequence in half, because the second half was a mirror image of the first. Why was that important? We could store twice as many differences in the same memory space of which we only had only a few K (yes K) to work with.

Hope some of you find this interesting, helpful or informative. Thanks, Scott, for what you taught me in college. You are greatly missed!

Bob





































root of num