Learn the most important control and control categories that every architect and developer should include in their projects.

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?

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?

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with Premium.
Start your 7-day free trial.

I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

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

After you answer that question, do you see a connection between sqrt and your answer?

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trialif (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.

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

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.

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?

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;

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?

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;

}

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?

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.

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?

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.

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?

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.

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

C#

From novice to tech pro — start learning today.

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with Premium.
Start your 7-day free trial.

Open in new window

Would this help?