finding prime numbers

[Cyran Meriel]

I found this solution online and it works but I cant understand the logic behind it..I understand that the break is important but still... i and j increases by the same amount and are always equal according to the statements. So for every loop j is equal to i so it should print 2,3,4,5,6 etc..
It says when j == i print i.. It cant jump over that statement to check if i%j == 0 and then go back to the print. Its not put in the right order to do that..

I've been thinking for hours but my human logic can't understand the programming / computer logic..

package träning;

public class Primeone {
	public static void main(String args[]) {
		for(int i = 2; i <= 100; i++)
		{
			for(int j = 2; j <= i; j++)
			{
				if(j == i)
				{
				System.out.println(i);
				}
				if(i%j == 0)
				{
					break;
				}
				}
			}
		}
}

[Henry Wong]

Cyran Meriel wrote:I found this solution online and it works but I cant understand the logic behind it..I understand that the break is important but still... i and j increases by the same amount and are always equal according to the statements. So for every loop j is equal to i so it should print 2,3,4,5,6 etc..
It says when j == i print i.. It cant jump over that statement to check if i%j == 0 and then go back to the print. Its not put in the right order to do that..

One is an inner loop to the other. They don't iterate together. In fact, for one iteration of the outer loop, the inner loop has to start from the beginning (2) until the end (or until it breaks).

Henry

[Cyran Meriel]

Henry Wong wrote:

Cyran Meriel wrote:I found this solution online and it works but I cant understand the logic behind it..I understand that the break is important but still... i and j increases by the same amount and are always equal according to the statements. So for every loop j is equal to i so it should print 2,3,4,5,6 etc..
It says when j == i print i.. It cant jump over that statement to check if i%j == 0 and then go back to the print. Its not put in the right order to do that..

One is an inner loop to the other. They don't iterate together. In fact, for one iteration of the outer loop, the inner loop has to start from the beginning (2) until the end (or until it breaks).

Henry

Where does it say that the inner loop has to start from the beginning after one iteration of the outer loop? I mean it says j++, so it has to add 1 for every loop right? So then it will increase, how can it reset as 2 then?

[Campbell Ritchie]

That is an inefficient way to find prime numbers. You do not notice the inefficiency because you are only searching up to 100.
The inner loop does not need to go up to i.

Find out about the Sieve of Eratosthenes which is a more efficient way to seek prime numbers.

[Cyran Meriel]

Campbell Ritchie wrote:That is an inefficient way to find prime numbers. You do not notice the inefficiency because you are only searching up to 100.
The inner loop does not need to go up to i.

Find out about the Sieve of Eratosthenes which is a more efficient way to seek prime numbers.

Yes, the guy that made the program said so himself. I will find a better way but I just want to understand this program first..I can't leave something that I don't understand, it will bug me constantly and I cant focus on new things. Especially when it seems it should be easy to grasp.

[Campbell Ritchie]

It starts from 2 then goes up to the value of the number. If it finds the number divides exactly, break; makes it try the next number.

As I said, find out about the Sieve.

[Campbell Ritchie]

Don't quote the whole of the previous post; that simply makes the discussion longer without adding new information.

When you finish the inner loop, while the outer loop is set to 17, the outer loop will move on one (18) and then you start the inner loop again with j = 2.

[Cyran Meriel]

We start with 2 both i and j is 2. So j == i so it prints i(2). It goes to i%j = 0 and it passes since it divides evenly, so it breaks. Now what you are saying is that it breaks only the j loop (i dont see the logic in this, but ok) so i becomes 3 and j is still 2.
3 is not equal to 2 so it cant print i. i%j is not 0 so it doesn't break right? It increases j instead with 1. So we have 3 and 3. It prints out 3 and i%j is 0 so it breaks again. So we have 4 and 2 this time. 4 does not equal 2 and it divides evenly so it breaks. now we have 5 and 2. its either equal or % = 0 so it increases j to 3. Same thing happens and with 4 as well so we have i & j = 5 now. It prints 5. etc..

I think I get it now, I had to write it in this way in order for it to make sense to myself. Please tell me if I got anything wrong.

[Henry Wong]

Cyran Meriel wrote:
Where does it say that the inner loop has to start from the beginning after one iteration of the outer loop? I mean it says j++, so it has to add 1 for every loop right? So then it will increase, how can it reset as 2 then?

In order to do the next iteration of the loop, the previous iteration has to complete (which includes break)... this means that the whole body of the outer loop has to complete. Arguably, the inner loop doesn't reset as 2. The inner loop just completed. And the next iteration of the outer loop is just running the inner loop (again).

So, let me ask you... where does it say that when a loop is encountered in the body of the loop, it only does one iteration -- saving the next iteration for the next iteration of the outer loop?

Henry

[Cyran Meriel]

Henry Wong wrote:
In order to do the next iteration of the loop, the previous iteration has to complete (which includes break)...
Henry

Thanks, I get it now

[Winston Gutkowski]

Cyran Meriel wrote:I think I get it now, I had to write it in this way in order for it to make sense to myself. Please tell me if I got anything wrong.

Nope, I think you've got it spot on. And I hate to say, but you'll have to do that sort of analysis any time you don't understand what's going on in a program.

Now: Once you've gone through it a bit further, see if you can write down, in English, why it finds a prime number. And feel free to post your explanation here.

And once you've done that: How do you think you might improve those loops?

Winston

PS - As for the break statement: I don't like seeing them in loops either, and they can often be avoided; but what you're describing IS how they work.

[Cyran Meriel]

Winston Gutkowski wrote:
Nope, I think you've got it spot on. And I hate to say, but you'll have to do that sort of analysis any time you don't understand what's going on in a program.

It finds prime by zeroing in on numbers that are not divided evenly by 2. If they do they are not prime. Simple explanation, but I can't manage to go further since my brain hurts at the moment. I'm positive that several of my brain cells committed suicide in the process of figuring out this program.

The problem I see in this program is that it's not effecting since it will check numbers that we already declared as primes. But to figure out a way thats more effective is too hard for me now since I started from scratch (no previous programming experience) a couple of days ago. There is so much basic information to take in and sort out, and then be able to recall it when making simple programs. It's a painful and slow process but I hope it will be easier in the near future.

I'll read up on Sieve later.

[Winston Gutkowski]

Cyran Meriel wrote:It finds prime by zeroing in on numbers that are not divided evenly by 2. If they do they are not prime...

OK, but that's not the whole story. Maybe try to go a bit further when your brain hurts less.

The problem I see in this program is that it's not effecting since it will check numbers that we already declared as primes.

Well spotted, and very nicely put.

But to figure out a way thats more effective is too hard for me...

Actually, I doubt that it is, but it sounds like you're "programmed out" at the moment.

Go have yourself a pint (if you're allowed) and watch something mindlless on TV. Sounds like you've earned it.

Winston

[Campbell Ritchie]

I would have thought TV would kill off OP's remaining brain cells

But the advice to do something completely different is spot on