Help understanding this small program

[insanepenguin]

// Find prime numbers between 2 and 100.
using System;
class Prime {
static void Main() {
int i, j;
bool isprime;
for(i=2; i < 100; i++) {
isprime = true;
// See if the number is evenly divisible.
for(j=2; j <= i/j; j++)
// If i is evenly divisible, then it’s not prime.
if((i%j) == 0) isprime = false;
if(isprime)
Console.WriteLine(i + " is prime.");
}
}
}

How does i/j test if the number is evenly divisible? and take the number 2 for example: i = 2 and j = 2, 2/2 = 1 so j is not incremented. 2%2 == 0 so shouldn't it be set to false even though 2 is a prime number?

Many Thanks!

[ddanbe]

The for loop on line 10 never gets executed for i = 2, so will print out as prime.
Check for it in the debugger by setting a breakpoint!
Or do it with pencil and paper.
You could speed up by printing out 2 in front of the loops(everybody knows it is prime) and make line 7 look like this for(i = 3; i < 100; i += 2)Everybody knows even numbers are not prime, so why should you test them?

[insanepenguin]

Hi ddanbe, good tip about only testing odd numbers!

for (j = 2; j <= i / j; j++)

could you explain what this does in relation to prime numbers? i.e. how does it check the number is divisible by 1 and itself, why is the j incremented?

thanks a lot

[ddanbe]

It never checks if a number is divisible by 1 because ALL integers are divisible by 1.
Now take a sheet of paper and a pencil, let's play computer the old way!
Consider we arrived at the situation were i=17 and we are at the start of the j-loop.
Because j=2 and i/j=8 we enter the j-loop and calculate i%j which is 1 so the if doesn't get executed. Let's put it in a table to make it more clear.
i = 17
j = 2
i/j = 8
i%j = 1
isPrime = true
We are still in the j-loop so next to these values write them again i stays the same
j augments by one and we do again some test and calculation so our table now becomes
i = 17 17
j = 2 3
i/j = 8 5
i%j = 1 2
isPrime = true true
Now continue this way untill you arrive at a condition where you get out of the j-loop.
You will know then whether 17 is a prime or not.
Practice with other numbers. I always found this a helpfull technique to know what was going on while debugging. Success!

[insanepenguin]

Now I know how the second for loop works it makes a lot more sense! is this right: the i/j is what gets me out of the loop, for example 17 isprime is true through every test and when it gets to 17/17 this fails the j <= i / j condition, leaving 17's isprime set to true.

The second loop is basically looking for any number that will divide i with no remainder thus making it false :)

[ddanbe]

In this age of internet etc. don't trow away your pencil and paper!
An even better way would be to test in the j-loop for the square root of i. :-/

[insanepenguin]

Thanks for your help, pen and paper is great! :D

[ddanbe]

for example 17 isprime is true through every test and when it gets to 17/17 this fails the j <= i / j condition, leaving 17's isprime set to true.

You almost got it but not completely. The j variable never becomes 17.
It stops at 5, see this complete paper and pencil table:
i = 17 17 17 17
j = 2 3 4 5
i/j = 8 5 4 3 because 5>3 it fails the condition j <= i / j so the j-loop ends here.
i%j = 1 2 1
isPrime true true true

[insanepenguin]

Ahh of course, j = 5 fails j <= i / j (3) so the loop stops there I finally understand both loops!. Sorry for being dense but why does it stop at that point, why doesn't it need to test further?

Many thanks

[ddanbe]

Well I'm not a specialist in number theory, but consider the number 12.
It has factors 1,2,3,4,6,12. Its square root is s=3,4641... So s*s = 12.
So if you can not find a factor < s you don't have to look for a factor > s.
This is somewhat how the test j <= i/j works. For the number 17 (square root = 4,1231) when j gets 5 you get out of the loop.
This is my perhaps a bit naive explanation, being an amateur math hobbyist.:|
Hope it helps and perhaps some math pros out here can give a more profound explanation.

[insanepenguin]

That makes sense, you don't need to test past the square root to test divisibility and if each test up to the square root leaves a remainder (i%j) it's a prime number.

I think maybe I'm a bit OCD about the maths involved when I should concentrate on learning how C# works!

Cheers

[ddanbe]

When it leaves no remainder it is a prime yu wanted to say I guess, so let's consider this solved then.
More questions, just ask! Happy computing :)

[insanepenguin]

Hi ddanbe, I meant that each modulus test leaves a remainder for primes like

i = 7
j = 2
i/j = 3
i%j = 1

thanks for your help and patience!