• Post Reply Bookmark Topic Watch Topic
  • New Topic

need help understanding how this code works: it generates prime numbers up to a certain number.  RSS feed

 
Greenhorn
Posts: 20
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm a java noob, I'm still learning pre-calculus and calculus so my math is shadey, and I'm bad at writing algorithims with diamond boxes and boxes, but heres the code and below is my attempt to understand it, but I need more clarity, if I don't understand how it works I won't learn anything.





Here is how I'm understanding it, I don't know how to write algorithims yet, so this is the best I can do, I use numbers and -> to indicate step by step process, my main misunderstanding is in the isPrime method, I just don't get it.


1.) count = 0
2.)number of primes per line = 10 ->
3.)while count < number of primes & if the counter is a prime (isPrime method below the code)

4.)count ++ ->
5.)if count reaches 10 -> space and go to next line
6.)else -> space without new line.

now the isPrime method is what I have trouble understanding,

number = 2 (to be tested for prime) -> either true or false (does this number variablea any different because of block scope?) ->
divisor = 2; divisor <= number / 2; divisor++)
if number % divisor == 0
return false, means it's prime which means it's printed
return true, which means it's not prime not printed.

what I don't understand is how the isPrime function works, can someone explain it to me?


when I become a better programmer I will return the favor and help people, that is my goal I want to teach and write software to solve problems.
 
Sheriff
Posts: 4289
127
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Write or type what each line does in isPrime() and post that.

Do you know what "%" does? It's a modulo. n % m returns the integer remainder after diving n by m.
 
Jeffrey Gutierrez
Greenhorn
Posts: 20
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Knute Snortum wrote:Write or type what each line does in isPrime() and post that.

Do you know what "%" does? It's a modulo. n % m returns the integer remainder after diving n by m.




1.) creates a method signature with an int as a parameter
2.) for loop, divisor = 2, divisor <= number (divided by) 2; divisor++) <- so if number 12, it becomes 6? then divisor becomes 3?
3.) 6/3 = 0 so it returns false, so 6 is not prime?

I really don't get it can someone explain this step by step I'm so confused.
 
Knute Snortum
Sheriff
Posts: 4289
127
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You've got some of it.

1) Set divisor from 2 up to number / 2
2) For each divisor
3) If divisor evenly divides number, return false
4) If you get through all divisors, return true

BTW, this is NOT a very good isPrime() function; it could have all sorts of improvements.
 
lowercase baba
Bartender
Posts: 12565
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
the for loop has several parts..


So when you first hit this line, it does the <first part>. This is where you can set up stuff. In this case, you declare a brand new, never seen before variable called "divisor", and set it equal to 2. This part will never run again as far as this loop is concerned (I say that because you can have a loop inside a loop, but we'll hold off on that for now).

The <second part> is the test to see if you should run the body of the loop this time. It is checked every time we come back to the beginning of the loop.

The <third part> is executed after you run through the loop body each time. It may never be called if the body never runs, but it's one way to change things so that you get out of your loop eventually (there are other ways).


So in your case, you have this:


The first time you hit this "for" line, you create a new variable and set it to 2.

We then do the check. Let's assume you passed in 9. is 2 <= 9 / 2 ? this becomes "is 2 < 4"? It is, so let's run the loop body:
number % divisor here becomes 9 % 2, which becomes 1. The if conidition fails, so we skip line 3. We now are done with the for-loop body. so we do the <third part>: divisor++. so divisor is now 3.

we go back to the top, and do part 2 again: is 3 < 9/2 (or 4). It is. so we enter the loop body.

is number % divisor == 0? well...9 % 3 becomes 0, and 0 == 0, so we enter the if body. it says "return false".

Return means "immediately leave this method, and tell whoever called me the answer is "false".
 
Jeffrey Gutierrez
Greenhorn
Posts: 20
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
fred rosenberger wrote:the for loop has several parts..


So when you first hit this line, it does the <first part>. This is where you can set up stuff. In this case, you declare a brand new, never seen before variable called "divisor", and set it equal to 2. This part will never run again as far as this loop is concerned (I say that because you can have a loop inside a loop, but we'll hold off on that for now).

The <second part> is the test to see if you should run the body of the loop this time. It is checked every time we come back to the beginning of the loop.

The <third part> is executed after you run through the loop body each time. It may never be called if the body never runs, but it's one way to change things so that you get out of your loop eventually (there are other ways).


So in your case, you have this:


The first time you hit this "for" line, you create a new variable and set it to 2.

We then do the check. Let's assume you passed in 9. is 2 <= 9 / 2 ? this becomes "is 2 < 4"? It is, so let's run the loop body:
number % divisor here becomes 9 % 2, which becomes 1. The if conidition fails, so we skip line 3. We now are done with the for-loop body. so we do the <third part>: divisor++. so divisor is now 3.

we go back to the top, and do part 2 again: is 3 < 9/2 (or 4). It is. so we enter the loop body.

is number % divisor == 0? well...9 % 3 becomes 0, and 0 == 0, so we enter the if body. it says "return false".

Return means "immediately leave this method, and tell whoever called me the answer is "false".


~_~_~_~_~_~_~_~__~_~__~__~_~_~_~_~_~_~_~~__~_~~_~_~_~_~_


and it continues
to evaluate true/false true being prime until the number 50 is reached?

let me give an example just to make sure I got this right,

1.) divisor starts with 2
2.) i pass 6, 6/2 = 3, 2<=3 is true, so the body runs
3.) 3 % 2 = 1, which makes divisor greater than number, so divisor becomes 3.
4.) 3 <= 3, true
5.) 3 % 3 = true
6.) it returns true, which means the number is prime, and 3 is a prime number.

do I have the right idea here?

thank you guys for help, heres a little program I found on the net that brought me so much joy, run it in your ide, then open text pad and it will type something automatically for you.


 
Knute Snortum
Sheriff
Posts: 4289
127
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

1.) divisor starts with 2
2.) i pass 6, 6/2 = 3, 2<=3 is true, so the body runs
3.) 3 % 2 = 1, which makes divisor greater than number, so divisor becomes 3.
4.) 3 <= 3, true
5.) 3 % 3 = true
6.) it returns true, which means the number is prime, and 3 is a prime number.


1) Right
2) Right
3) number is still 6, divisor is 2, 6 % 2 = 0 (that is, there is no remainder left over after you divide 6 by 2). Return false, 6 is not prime. You're done.
 
fred rosenberger
lowercase baba
Bartender
Posts: 12565
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You really don't need to quote my entire post...just post the relevant part (if any)

Jeffrey Gutierrez wrote:
and it continues
to evaluate true/false true being prime until the number 50 is reached?

I was really just talking about what happens inside your isPrime() method. Generally, you want to break programs down into their pieces. so I did an example of passing 9 into the method. You can play with a few other values to see what shakes out. But then, once you have a good idea of how the details of isPrime() works, you can now move to a higher level of your program...This part:



So this is a while loop. If we ignore the details of what's inside this body, we see we have a counter (count), a limit on the counter (numberOfPrimes) and a number. we start testing with the number == 2, and do <something>. If that returns true, we increment count (i.e. we found one more of what we want...whatever it is). then, regardless of what we found, we increment number to test the next number.

basically, we are going to test 2, then 3, then 4...for <something>. Some will be what we want, some won't. When we've found enough, we quit.

What's cool here is what we are testing for could be anything. Right now, it's for prime-ness. But it would be trivial to replace the isPrime() call with something like isPerfectNumber(), or isMersenne(), or isPerfectSquare()...etc.

Programming is kind of like legos. you can add and remove pieces until you get exactly what you want.
 
Jeffrey Gutierrez
Greenhorn
Posts: 20
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
fred rosenberger wrote:You really don't need to quote my entire post...just post the relevant part (if any)

Jeffrey Gutierrez wrote:
and it continues
to evaluate true/false true being prime until the number 50 is reached?

I was really just talking about what happens inside your isPrime() method. Generally, you want to break programs down into their pieces. so I did an example of passing 9 into the method. You can play with a few other values to see what shakes out. But then, once you have a good idea of how the details of isPrime() works, you can now move to a higher level of your program...This part:



So this is a while loop. If we ignore the details of what's inside this body, we see we have a counter (count), a limit on the counter (numberOfPrimes) and a number. we start testing with the number == 2, and do <something>. If that returns true, we increment count (i.e. we found one more of what we want...whatever it is). then, regardless of what we found, we increment number to test the next number.

basically, we are going to test 2, then 3, then 4...for <something>. Some will be what we want, some won't. When we've found enough, we quit.

What's cool here is what we are testing for could be anything. Right now, it's for prime-ness. But it would be trivial to replace the isPrime() call with something like isPerfectNumber(), or isMersenne(), or isPerfectSquare()...etc.

Programming is kind of like legos. you can add and remove pieces until you get exactly what you want.
Thats a brilliant idea if there was a thank you button I'd up your rep!

I hate to ask so many questions, but I'm adamant about becoming a computer scientist, can you explain to me in the post above the one I quoted where you said "it's still six"? can you explain how that works, I need all the little details to integrate it into my mind.


 
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jeffrey Gutierrez wrote:I'm a java noob, ... I don't know how to write algorithims yet ....

All irrelevant. Sorry, but it just is.

so this is the best I can do,..

No it isn't. You KNOW what a prime number is .... don't you?

So, do it this way:

If I gave you a number - say 323 - how would YOU work out whether it was a prime number?

Work it out yourself, and write down EVERY STEP in detail.

Now think about how you might translate that to Java.

NOW go back and have a look at the code.

Does it make any more sense now?

You cannot write a Java program to do something you don't understand - unless you're extraordinarily lucky.

HIH

Winston
 
Jeffrey Gutierrez
Greenhorn
Posts: 20
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Winston Gutkowski wrote:
Jeffrey Gutierrez wrote:I'm a java noob, ... I don't know how to write algorithims yet ....

All irrelevant. Sorry, but it just is.

so this is the best I can do,..

No it isn't. You KNOW what a prime number is .... don't you?

So, do it this way:

If I gave you a number - say 323 - how would YOU work out whether it was a prime number?

Work it out yourself, and write down EVERY STEP in detail.

Now think about how you might translate that to Java.

NOW go back and have a look at the code.

Does it make any more sense now?

You cannot write a Java program to do something you don't understand - unless you're extraordinarily lucky.

HIH

Winston
Ok I think I figured this out, it counts up to 50 and checks every number starting with 2 which is prime, and whether or not it has a remainder or not it gets printed?

because I only know how to find primes by division, prime factorization, divsibiliity by 2, and I know that if you divide a prime number by any number it should have a remainder because a prime can only be divisible by 1 and itself.

 
fred rosenberger
lowercase baba
Bartender
Posts: 12565
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Again...Please to NOT quote an entire post. All you really need to to is hit the Post Reply button. If you do want to quote something, please ONLY quote the relevant part.

Programmers are quite literal. We're also very specific. We don't like ambiguity. So when you say "it counts up to 50", it is unclear what you mean. It has to count higher than 50, because when you run it, it is printing values in the 200+ range.

Can you be more specific there? (I'm doing this because you need to practice writing clear specs so others can understand what your code does).
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!