programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Tim Cooke
• Devaka Cooray
• Ron McLeod
• Jeanne Boyarsky
Sheriffs:
• Liutauras Vilda
• paul wheaton
• Junilu Lacar
Saloon Keepers:
• Tim Moores
• Stephan van Hulst
• Piet Souris
• Carey Brown
• Tim Holloway
Bartenders:
• Martijn Verburg
• Frits Walraven
• Himai Minh

# finding prime numbers

Ranch Hand
Posts: 32
• Number of slices to send:
Optional 'thank-you' note:
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..

author
Posts: 23928
142
• Number of slices to send:
Optional 'thank-you' note:

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
Ranch Hand
Posts: 32
• Number of slices to send:
Optional 'thank-you' note:

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?

Marshal
Posts: 76885
366
• Number of slices to send:
Optional 'thank-you' note:
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
Ranch Hand
Posts: 32
• Number of slices to send:
Optional 'thank-you' note:

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
Marshal
Posts: 76885
366
• Number of slices to send:
Optional 'thank-you' note:
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
Marshal
Posts: 76885
366
• Number of slices to send:
Optional 'thank-you' note:
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
Ranch Hand
Posts: 32
• Number of slices to send:
Optional 'thank-you' note:

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
author
Posts: 23928
142
• 1
• Number of slices to send:
Optional 'thank-you' note:

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
Ranch Hand
Posts: 32
• Number of slices to send:
Optional 'thank-you' note:

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

Bartender
Posts: 10780
71
• 1
• Number of slices to send:
Optional 'thank-you' note:

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
Ranch Hand
Posts: 32
• Number of slices to send:
Optional 'thank-you' note:

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
Bartender
Posts: 10780
71
• Number of slices to send:
Optional 'thank-you' note:

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
Marshal
Posts: 76885
366
• 1
• Number of slices to send:
Optional 'thank-you' note:
I would have thought TV would kill off OP's remaining brain cells

But the advice to do something completely different is spot on

 I will open the floodgates of his own worst nightmare! All in a tiny ad: the value of filler advertising in 2021 https://coderanch.com/t/730886/filler-advertising