Solved

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

Posted on 2014-10-18
341 Views
This is my method that checks if a parameter named "num" 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;

return true;
}

It works 100% of the time. However, my instructor wants us to use Math.Sqrt() in the code. So I changed the for loop to this.

for (int j = 2;  j < Math.Sqrt(num);  j++)

The change slightly decreased its effectiveness-- now it works 99.8% of the time.  It's not 100% because every once in a while it calculates a number to be prime when in fact it is not prime. For example, for numbers 1 to 10000, the numbers that the method incorrectly identifies as prime are shown below.

4
9
49
121
289
361
529
841
961
1369
1681
2209
2809
3599
3721
5041
5183
5329
6241
6889
9409

Does anyone know how to correct this minor glitch?
0
Question by:MBarongan
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• 11
• 9
• 2
• +2

LVL 34

Expert Comment

ID: 40389649
`````` 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;
}
``````

Would this help?
0

LVL 32

Accepted Solution

phoffric earned 500 total points
ID: 40389655
For this assignment, we should not really be giving out answers.

I would start off with the lower number glitches (e.g., 4, 9, 49) and step through the program using a debugger. This article describes a C++ debugger, but in VS 2008 through 2013, most of the basic steps still work for C#.
http://www.experts-exchange.com/Programming/Languages/CPP/A_2688-Microsoft-Visual-Studio-2008-Express-C-Quick-and-Dirty-Debugger-Tutorial.html

Easy question - what do most of your glitches have in common? Just look at the first few. 4, 9, 49, 121

0

Author Comment

ID: 40389670
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;

0

Author Comment

ID: 40389688
Clarification:

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

LVL 32

Expert Comment

ID: 40389692
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.
0

LVL 32

Expert Comment

ID: 40389695
>> 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?
0

LVL 32

Expert Comment

ID: 40389698
btw - I always thought 2 was a prime.
0

Author Comment

ID: 40389705

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;
0

LVL 32

Expert Comment

ID: 40389708
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?
0

Author Comment

ID: 40389712
Yeah you're right. I need to work on this some more.
0

LVL 32

Expert Comment

ID: 40389716
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.
0

Author Comment

ID: 40391191
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;
}
0

LVL 32

Expert Comment

ID: 40391198
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?
0

Author Comment

ID: 40391247
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.
0

LVL 32

Expert Comment

ID: 40391267
>> 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?
0

Author Comment

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

LVL 84

Expert Comment

ID: 40391358
Is "half" the relationship between 1000000 and Math.Sqrt(1000000)?
0

Author Comment

ID: 40391380
I meant half the number of processor clock cycles to run the program to completion.
0

LVL 84

Expert Comment

ID: 40391386
So what limits the number of processor clock cycles to run the program to completion?
0

Author Comment

ID: 40391427
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.
0

LVL 32

Expert Comment

ID: 40391435
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?
0

Author Comment

ID: 40391476
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.
0

Author Comment

ID: 40391480
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.
0

LVL 1

Expert Comment

ID: 40391855
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
0

Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

The article shows the basic steps of integrating an HTML theme template into an ASP.NET MVC project
Q&A with Course Creator, Mark Lassoff, on the importance of HTML5 in the career of a modern-day developer.
This tutorial will introduce the viewer to VisualVM for the Java platform application. This video explains an example program and covers the Overview, Monitor, and Heap Dump tabs.
This video will show you how to get GIT to work in Eclipse.   It will walk you through how to install the EGit plugin in eclipse and how to checkout an existing repository.
Suggested Courses
Course of the Month7 days, 22 hours left to enroll