This week's book giveaway is in the Reactive Progamming forum.We're giving away four copies of Reactive Streams in Java: Concurrency with RxJava, Reactor, and Akka Streams and have Adam Davis on-line!See this thread for details.
Win a copy of Reactive Streams in Java: Concurrency with RxJava, Reactor, and Akka Streams this week in the Reactive Progamming forum!
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
• Liutauras Vilda
• Junilu Lacar
• Jeanne Boyarsky
• Bear Bibeault
Sheriffs:
• Knute Snortum
• Tim Cooke
• Devaka Cooray
Saloon Keepers:
• Ron McLeod
• Stephan van Hulst
• Tim Moores
• Tim Holloway
• Carey Brown
Bartenders:
• Piet Souris
• Frits Walraven
• Ganesh Patekar

# Help with a Prime Number 'For Loop' Program Please?

Greenhorn
Posts: 28
Hello everyone,
I am studying the Oracle Beginner's Guide and I have a problem with an assignment at the end of chapter 2
It asks me to create a program to find all the prime numbers between 2 and 100. And to do this it employs the use of 2 'For Loops' one nested insde the other.
I had no way of creating the program because both my Java and maths would not allow so I checked the answer and it was this:

The reason for my confusion is that I cannot understand how the second for loop is working (for int j)

I was hoping someone could look at this code and explain in as simple a way possible why this is the case. I do think I understand what the maths is doing on the 1st and 2nd loops because of the values of each int at the time of the loop iterations and even the results of the boolean expression at the time of each loop.

In the end I replaced the nested for loop by just declaring int j to be 2, and then using the final if statement as well, you get the correct result ( I think) although it misses the number 2 from the resulting list?. As I have tried to show you below:

That makes me even more confused by the syntax of the inner For loop using int j.
I have tried to study prime numbers and I do sort of  understand that it is any number that is only divisible by 1 or itself and will not be any even number apart from 2.

I guess that int j has to be incremented at certain points for this program to work, and it does this by virtue of the expression in the inner for loop.
Could anyone be so kind as to try to break this down for me, I know I am asking an awful awful lot, and maybe I just need to have a clearer understanding of Maths, but it might be that I don't fully understand the function of loops, and if this is the case could you please give me some pointers? if not I will just have to shelve this until my understanding improves and that's fine as well I guess.

Thank you very much for taking the time here.

cliff.

Marshal
Posts: 14039
234
First off, proper indentation of code is very important. Improper indentation make the code confusing and even misleading.

This is not properly formatted / indented.

This is properly formatted / indented

Proper indentation is not just for aesthetic purposes. Proper indentation makes the structure of the program logic clear, shows which statements go together, and informs you about the order that statements will be executed.

In general, statements that are similarly aligned will be executed one after another from top to bottom. Any statements that are indented under another statement, like how line 8 is indented under line 7, indicates another level of detail that is subjugate to the first.

So, the for-loop on line 7 really has only three "subjugate" or detailed statements: the assignment statement on line 8, the for-loop that starts on line 11, and the if-statement on line 15. These will be executed one after another on each iteration of the for-loop on line 7.

Similarly, line 13 is indented one level from the for-loop on line 11. This makes it the only statement that is executed repeatedly by that for-loop. The if-statement below that on line 15 will be executed after the for-loop on line 11 gets done.

One last thing to note about indentation: In Java, the compiler doesn't care about indentation. Indentation is only helpful to the human reader. This in contrast with a language like Python, which has much stricter rules about indentation. But this is Java, so make it easy on yourself and others and make sure your code is properly indented.

EDIT: if the use of "subjugate" above seems weird, just substitute "subordinate" - what I mean is essentially that the indented statements are dependent on the "ruling" statement in some way. These subordinate statements are often said to be "the body" of the first statement. That is, line 13 forms the body of the for-statement on line 11. Line 11 itself is in the body of the for-statement on line 7 and is "sibling" of the statements on lines 8 and 15.

Junilu Lacar
Marshal
Posts: 14039
234
That code you gave is wrong.

The for-loop on line 11 should be this:

Ideally, you'd enclose the body of the for-loop with braces, like this:

Always do that, even if the body has only one statement. This makes your intent clear and also helps avoid bugs in the future if you decide to add more statements to the body.

Junilu Lacar
Marshal
Posts: 14039
234
• 1
Using better names can also help you make your program make more sense. The variable names i and j are not very meaningful. Look at the same code below that uses different names (I also moved some of the declarations around):

Read that code and see if you have a better time understanding how it works now.

Cliff Black
Greenhorn
Posts: 28
Firstly Junilu Lacar,

I was really being lazy about the rules of indentation and phrasing here. There is no excuse, I guess my confusion about the program had me neglecting other important principles about Java and I am glad you have made me understand just how important it really is. I never really understood about subjugation and relationships between statements. Now I have a better understanding and will take greater care to learn and observe this rule in future.
Thank you once again I really appreciate that.

In regards to the code that you identified as being wrong:

This is exactly where I am left confused. The book has the code exactly as you saw it,  ( j <= i/j) and I think my inability to understand this syntax for exactly what it is doing within the loop and the program as a whole is why I am lost.
The way you have put it makes much more sense and also the fact that you used curly braces to enclose the statements inside this inner loop is exactly what I expected to see, and the absence of them in the book confused me as well, so thank you for telling me that they should be included here.

So if you would allow me to try to explain the second For loop as I think I understand it please.

it says  J is equal to 2, then if  J (meaning the value 2) is less than or equal to the result of  i (2) divided by j (2) then increment the value of j (2) by one if the result of this expression is true, if it is not true then the value of j remains the same for the next loop iteration.

That is what my head is seeing and I guess I may be way off the mark, maybe over or under thinking the expression, which leads me to what you told me in your latest post. you said that it might be better to change the name of the variables into something more meaningful.

so you declared the divisor as an int within the loop instead of outside it which makes sense, you gave it an initial value of 2, and then you used the expression divisor <= number/2. Right here is 2 the same as the int divisor, being the value that 'divisor' has in this iteration? in other words 'divisor <= number / divisor; divisor++'

And the increment (++) operator at the end of the For loop statement, does it turn the value of the divisor into 3 after the result is true at the end of a given iteration? it seems that if you always divide by two, then the output result of prime numbers does not included the number 2. So this expression is making sure that even though 2 is an even number, it will still be evaluated as being prime when tested using the For loop expression.
How exactly I cannot see but the point is I don't think I understand what the inner for loop is saying in simple terms and I hoped that you could say?. Or otherwise tell me if I should ignore this program and stick to more simple programs until I get a better grasp of things.
I didn't expect an assignment like this to appear at the end of chapter 2.

Thank you Junilu,
I am so sorry to be a nuisance

cliff

Sheriff
Posts: 6266
167

Cliff Black wrote:I was really being lazy about the rules of indentation and phrasing here. There is no excuse, I guess my confusion about the program had me neglecting other important principles about Java and I am glad you have made me understand just how important it really is. I never really understood about subjugation and relationships between statements. Now I have a better understanding and will take greater care to learn and observe this rule in future.

You can learn HowToFormatCode (that's a link) in this wiki.

In regards to the code that you identified as being wrong:

...

it says  J is equal to 2, then if  J (meaning the value 2) is less than or equal to the result of  i (2) divided by j (2) then increment the value of j (2) by one if the result of this expression is true, if it is not true then the value of j remains the same for the next loop iteration.

I like to think of the middle express as "while".  So, set j to 2, while j <= j/i, increment j.

Junilu Lacar
Marshal
Posts: 14039
234
It seems you're not quite clear on what the different clauses of the for-statement header do and when they are evaluated. Rather me explaining them, I suggest you study this first: https://docs.oracle.com/javase/tutorial/java/nutsandbolts/for.html

Marshal
Posts: 65782
250

Cliff Black wrote:. . . . The book

Please always tell us which book, to reduce copyright problems and allow us to verify the original. Does your book show you that sort of indentation? I hope not.

. . . it says  J is equal to 2, then if  J (meaning the value 2) is less than or equal to the result of  i (2) divided by j (2) then increment the value of j (2) by one if the result of this expression is true, if it is not true then the value of j remains the same for the next loop iteration.

That is what my head is seeing . . .

. . . which is more than I am seeing. Good grief! Does any book really say that sort of thing? Big J and small j and small i all together! If you wanted to make something difficult to understand, you could hardly do better.

. . .

Doesn't your book explain the inner loop? Have you copied it exactly? I don't like to see <= in for loops, because people are used to 0‑based indices and < works a lot better with 0‑based indices. Did they explain why they are using number/2, which apart from being incorrectly spaced, is not in my opinion the best continuation condition? And did they really print line 7 like that? The compiler can read it, I can read it, but it is a good example of how not to indent an if statement.
I ran your code and got a correct list of prime numbers. It might print prime numbers, but it is inefficient because it does nothing to record those numbers anywhere.

What the inner loop does is go through smaller numbers and see whether they divide exactly into your potentially prime number. If any smaller number divides, then the number you are tesing isn't prime. If you have a number like 91, however, you will test 4 and 6 as divisors when you know they can't divide because you already know 2 and 3 won't divide exactly into 91.

Junilu Lacar
Marshal
Posts: 14039
234
The loop termination clause is divisor < number/2 which essentially says "execute the body of the loop if divisor is less than half the number; otherwise, terminate the loop"

Think about it, if you were to test if 23 was prime, you would only try divisors from 2 up to 11, right? Why go up to 12 when you know that 12 is more than half of 23 so it can't possibly be a whole divisor of 23. Likewise for any number greater than 12. That's why your upper limit for divisor values is half the number you're checking to see if it's prime. There's no point in going all the way up to the number itself.

Campbell Ritchie
Marshal
Posts: 65782
250
But there is a better bound; if you have tried dividing 23 by 5 and smaller numbers, you know it is a prime number. Actually you will know 23 is prime if you find you can't divide it by 3.

Cliff Black
Greenhorn
Posts: 28
Hello,
sorry for causing all these worries,
I thank you both Junilu Lacar  and Campbell Ritchie for taking all this time to look at my issue.

Firstly, yes Junilu I think you are right in 'sign posting' me to more tutorials, because I am aware that this problem goes way beyond my level of understanding in terms of both Java and Maths. So I will go and look at that.

The Name of the book is 'Java A Beginner's Guide, Sixth Edition by Oracle' Author Herbert Schildt. And No Campbell Ritchie, the book does not show that sort of indentation. That was my poor representation of the code in the book which Junilu correctly pointed out to me was not properly reproduced. I am aware of this need for improvement. And in regards to my attempt at an explanation of the inner for loop;

I wasn't even aware that I wrote a mix of both small and capital letter j, I only meant to write a small j throughout in my explanation but of course being me, I didn't check what I wrote and so confused you further still. I do apologise for that sincerely because you are taking the time to examine my problem for me which I do appreciate very much.

I should have written this:

(it says  j is equal to 2, then if  j (meaning the value 2) is less than or equal to the result of  i (2) divided by j (2) then increment the value of j (2) by one if the result of this expression is true, if it is not true then the value of j remains the same for the next loop iteration.

That is what my head is seeing)

You have both gone into the ways in which the code seeks to discover the prime numbers using the  divisor, for loops and evaluations, and you have both provided a lot of alternative ways of using the code to achieve this outcome which are very detailed, thank you.

As I suspected, it is a bit difficult for me to grasp in full because of my level of maths and java at present. Even so, both you still have helped me to see a little clearer where I need to be which is amazing for me right now so thank you very much.
I will look at the link Junilu has provided and try to improve my basic maths which I am studying right now. And then I might try to look at Chapter 3 in a while.

Thanks again you guys,

cliff

Sheriff
Posts: 24654
58

Cliff Black wrote:The book has the code exactly as you saw it,  ( j <= i/j)

Although the code you posted just above that had something different:

There's some confusion there, but maybe it's mine. I didn't think the previous posts specifically discussed that division as an issue, but it's quite possible that I missed that.

Cliff Black
Greenhorn
Posts: 28
Hello Paul Clapham,
You are correct, I am the gift that keeps on giving here it seems.
Thank you for spotting yet another error of mine. I was quite flustered when I made the initial post and so I made a lot of neglectful errors in trying to reproduce the program, Junilu Lacar spotted the error as you did, but in correcting it he gave me alternative coding using the variable 'divisor' instead of 'j' which threw me, and so I never even realised that he was pointing to a typing error of mine in the first place. I have only just realised. So thank you.
I think I have received all the feed back I am going to get in regards to this query, but just to be neat and clear here is the correct coding, (I hope):

Thank you once again for checking and for your feedback,

cliff

Junilu Lacar
Marshal
Posts: 14039
234

Cliff Black wrote:I think I have received all the feed back I am going to get in regards to this query, but just to be neat and clear here is the correct coding, (I hope)

Hoping does not make a program correct. The code you posted does not look any different from what you had originally: not properly formatted and indented, poor variable names, and incorrect results.

Junilu Lacar
Marshal
Posts: 14039
234

Campbell Ritchie wrote:But there is a better bound; if you have tried dividing 23 by 5 and smaller numbers, you know it is a prime number. Actually you will know 23 is prime if you find you can't divide it by 3.

I think efficiency is the least of OP's worries at this point.

Cliff Black
Greenhorn
Posts: 28
Hello Junilu,

yes, that is because I made a draft of the code in note pad to create the original post. The one that you correctly identified as being poorly formatted. I did say that I would take your advice on board and I have, But in trying and rushing to answer the last post from Paul Clapham, I simply used the original draft again (which I did not correct yet due to lack of time). Had I taken the time to write the program out again instead of copying and pasting, you bet I would have done what you said, and not appearing to have totally ignored you. I simply rushed to answer another post.

but be assured I will not do that again here, the next time I ask for your help. The (hoping) I was referring to was the hope that the mix up in the inner loop that was identified by Paul Clapham was corrected. I at least know that formatting is to be done in a specific and correct way, I just forgot to re-do my original draft.

Sorry about that Junilu Lacar, and thanks for continuing to feedback on my posts.

cliff

Marshal
Posts: 7178
491
Hi Cliff,

Please post your current updated code and please tell us if you still have some issues with it.

Cliff Black
Greenhorn
Posts: 28
Thanks Liutauras Vilda,

I appreciate your offer of help very much.
Junilu Lacar did fully correct my code phrasing/positioning, and offered me an alternative way of naming and positioning the variables concerned in the 'for loops' to help me think of the expressions and statements in a clearer way.

It did help to that end and it also made me realise that I have to work on my Maths in general maybe a bit more before I am ready to tackle java above the very basic levels.
I am fine with that, and very grateful for the feedback.
here is the code he gave:

Thanks again,
cliff

Junilu Lacar
Marshal
Posts: 14039
234
The code I provided is not very efficient but I thought it best to focus on the for-loop mechanics and variable names first. If you have a better understanding of how that code works now, you might want to consider some of Campbell's points about efficiency. See this article for information that's relevant to efficiency of the brute force approach you're using: https://medium.com/swlh/the-prime-number-test-a-brute-force-approach-a25b9d6b231

Paul Clapham
Sheriff
Posts: 24654
58
• 1

Cliff Black wrote:... I have to work on my Maths in general maybe a bit more...

I'm a math guy and I noticed right away that if i and j are positive integers then j <= j/i is only true when i = 1. But of course you were struggling with for-loop mechanics and code indentation and so on, so that sort of thing would be the last thing you noticed. When you're debugging code the brain gets very focused, trust me, I know.

On the other hand, I've been writing programs for many years now and I never ever needed to know anything about prime numbers while writing those programs. Teachers give that sort of assignment because it's a non-trivial use of loops so it's presumably helpful for people learning about loops.

Cliff Black
Greenhorn
Posts: 28
Thank you guys,
I love Java and will keep going, your encouragement means a lot.

Thanks.

Greenhorn
Posts: 2
This looks mathematical problem.
j <= i/j.   =>  j square < i  => j  should go as far as sqrt of i.  not i/2.

Campbell Ritchie
Marshal
Posts: 65782
250
KH: welcome to the Ranch

Please explain what the formula you wrote means. Why are you using the implies operator? You are right that you should noeed not need to test divisors larger than the square root of the argument.

noeed??? I have corrected it to something that actually makes sense.noeed

Ranch Foreman
Posts: 266
12
Hello .

There is an efficient algorithm called the sieve of Erasthotene. It does a double loop but stores all the multiples of a prime number, so we don't check them twice since we already know they are a multiple and cannot be prime. If you are still interested Cliff, I can try to explain it simply?

And yes, the loop should go to the square root of n, because we are looking for a geometric mean value and not arithmetic mean value. The reason is that when we multiply numbers, their mean is not calculated the same way than than when we add numbers.

Campbell Ritchie
Marshal
Posts: 65782
250
• 1
Good to see you back.
Yes, a Sieve would be much a more efficient algorithm, but the OP is using a technique which doesn't record prime numbers, simply printing each individually.

D.J. Quavern
Ranch Foreman
Posts: 266
12

Campbell Ritchie wrote:Good to see you back.

Thank you! Good to speak to you again too !

Campbell Ritchie wrote:Yes, a Sieve would be much a more efficient algorithm, but the OP is using a technique which doesn't record prime numbers, simply printing each individually.

What does the OP mean?

Liutauras Vilda
Marshal
Posts: 7178
491

D.J. Quavern wrote:

Campbell Ritchie wrote:Yes, a Sieve would be much a more efficient algorithm, but the OP is using a technique which doesn't record prime numbers, simply printing each individually.

What does the OP mean?

D.J. Quavern, don't hesitate to refer Campbell to this tutorial in case he haven't read it: https://coderanch.com/wiki/659778/Real-Words

On a more serious side, I wouldn't be suprised if he actually wrote it

OP means original poster

D.J. Quavern
Ranch Foreman
Posts: 266
12
I thought for a second that it had to do with an OPerative system of some kind!

Can't even joke!
Screenshot-2019-09-21-at-20.37.41.png

Campbell Ritchie
Marshal
Posts: 65782
250
• 1

Liutauras Vilda wrote:. . . I wouldn't be suprised if he actually wrote it . . .

No, only part of it.

Campbell Ritchie
Marshal
Posts: 65782
250
• 1
OP means the person with OP against their name.

And sorry.

D.J. Quavern
Ranch Foreman
Posts: 266
12
No worries .
I will make sure to use OP in some context where I can sound smart.

Campbell Ritchie
Marshal
Posts: 65782
250
• 1
. . . but I have shown it makes you sound stupid

D.J. Quavern
Ranch Foreman
Posts: 266
12
You never sound stupid. But now I feel we are deriving further and further from what the Original Poster wanted .

If Cliff is back and wishes so, I can explain the sieve

Campbell Ritchie
Marshal
Posts: 65782
250
• 1
Why not explain anyway. And work out how to get all prime numbers up to 2147648483. Hint.

Greenhorn
Posts: 16
this is my java code for testing of the prime numbers:

It's my pleasure when you use it in your programs

Campbell Ritchie
Marshal
Posts: 65782
250
What about negative numbers, 0 and 1?

Manuel Prochnow
Greenhorn
Posts: 16

Campbell Ritchie wrote:What about negative numbers, 0 and 1?

please check the wikipedia for definition

definition of prime numbers

you find prime numbers starts with 2. that the smalest prime number.

Knute Snortum
Sheriff
Posts: 6266
167
Yes, but your method returns true with a parameter of 1, -1, or the opposite of any prime number.

Manuel Prochnow
Greenhorn
Posts: 16

Knute Snortum wrote:Yes, but your method returns true with a parameter of 1, -1, or the opposite of any prime number.

thank you for the hint.

 I love a woman who dresses in stainless steel ... and carries tiny ads: Java file APIs (DOC, XLS, PDF, and many more) https://products.aspose.com/total/java