This week's book giveaways are in the Jython/Python and Object-Oriented programming forums.
We're giving away four copies each of Machine Learning for Business: Using Amazon SageMaker and Jupyter and Object Design Style Guide and have the authors on-line!
See this thread and this one for details.
Win a copy of Machine Learning for Business: Using Amazon SageMaker and JupyterE this week in the Jython/Python forum
or Object Design Style Guide in the Object-Oriented programming forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
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 all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Bear Bibeault
  • Paul Clapham
  • Jeanne Boyarsky
  • Knute Snortum
Sheriffs:
  • Liutauras Vilda
  • Tim Cooke
  • Junilu Lacar
Saloon Keepers:
  • Ron McLeod
  • Stephan van Hulst
  • Tim Moores
  • Tim Holloway
  • Carey Brown
Bartenders:
  • Joe Ess
  • salvin francis
  • fred rosenberger

finding prime numbers

 
Ranch Hand
Posts: 32
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 23855
141
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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: 67520
257
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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: 67520
257
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 67520
257
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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: 23855
141
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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: 10777
71
Hibernate Eclipse IDE Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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: 10777
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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: 67520
257
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I would have thought TV would kill off OP's remaining brain cells

But the advice to do something completely different is spot on
 
Could you hold this puppy for a sec? I need to adjust this tiny ad:
Java file APIs (DOC, XLS, PDF, and many more)
https://products.aspose.com/total/java
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!