programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

prime number?

Mike Mo
Ranch Hand
Posts: 40
So my professor has tasked us with trying to figure out how to write a program that can determine if a given input int is a prime number or not. we havent learned about any sort of "getPrime" method or anything from the given math methods that would do that so she wants us to use critical thinking. its not an assignment, its just a "think about this before next class" then we will discuss it then.

my thoughts were maybe using a modulus somehow but i cant figure out how i would do it. any help or tips would be appreciated.

as i said this i just extra think about it before class on wednesday material.

thanks!

Daniel Andres
Ranch Hand
Posts: 94
3
If you know that modulus gives the remainder of a division then it is really easy from there. It is the same process as if you were doing math on a piece of paper. What determines a number being odd? Likewise, when is it an even number?

Daniel Andres
Ranch Hand
Posts: 94
3
My apologies. I read odd and not prime.

Mike Mo
Ranch Hand
Posts: 40
Daniel Andres wrote:My apologies. I read odd and not prime.

no problem :P

my idea of using modulus (%) is just a hunch so dont think that I "know" anything haha

something in my brain screams modulus to me but i cant for the life of me figure out why or how i would use that.

Paul Clapham
Sheriff
Posts: 22828
43
Let's try something specific: How would you decide whether 2701 was prime or not?

Daniel Andres
Ranch Hand
Posts: 94
3
Well at least you didn't get prime and odd confused :|

You could use modulus for instance to determine if the number is divisible by 2 then, with the exception of the number 2 itself, you'll know it is not a prime number.
This program is fun to code. By doing a few calculations with modulus (or regular division for that matter) it is very easy to determine the answer. I really don't know how close of a hint we can give in here since we can't provide solutions. But if you know that a prime number can only be divided by 1 and itself then it shouldn't take you too long to figure it out!

Mike Mo
Ranch Hand
Posts: 40
• 1
Paul Clapham wrote:Let's try something specific: How would you decide whether 2701 was prime or not?

had to look it up which i was trying to avoid but i suppose you would take sq rt of 2701 which is ~51.9. then you would divide 2701 by all the prime #'s under or equal to 51. if none of them divide evenly then that number is prime.

if i understood the equation properly.

Paul Clapham
Sheriff
Posts: 22828
43
Yup, that sounds right.

Only it's more complicated than you really need -- for example that part about dividing by all the prime numbers <= 51 could be a problem because you'd have to pause and figure out whether each of those numbers was prime, wouldn't you? A simpler way to do it would be to divide by all the numbers between 2 and 51 inclusive (not 1 and 51, every number is divisible by 1). Remember, this is just a beginner exercise, you don't have to come up with the ultimate and most perfect method on your very first try. Just something which works is good enough.

Daniel Andres
Ranch Hand
Posts: 94
3
Ohhh never mind! It is more elaborate than that. I want to program this now... you're on the right track with taking the square root of the number and then dividing by the prime numbers but then again.. If you're dealing with a big number the square root could be a 3 digit number. How to ensure that all the preceding numbers are prime numbers???

Sneaky little program

Mike Mo
Ranch Hand
Posts: 40
Daniel Andres wrote:Ohhh never mind! It is more elaborate than that. I want to program this now... you're on the right track with taking the square root of the number and then dividing by the prime numbers but then again.. If you're dealing with a big number the square root could be a 3 digit number. How to ensure that all the preceding numbers are prime numbers???

Sneaky little program

yeah this would be kinda a pain in the ass for a 4th week java student with absolutely no clue for the most part. xD

my thing with this whole class so far has been that i have an issue with learning "half ass" ways to do things. if there is a correct way and 5 "dumbed down" ways i would rather learn the hard way that is correct 100% of the time. my grandpa always said that the hard was is the easy way. if you get the work done now(the hard way) then later on when you want to do something, the work is done and you can do that. this makes you realize at that time that the hard was was in fact the easy way. this has proven to be true even when i didnt follow it haha hes a smart man. so i try to apply this to everything within reason in my life. so i guess in short i dont really want to have to learn a dumbed down way of doing something bc its a waste of time. if there is a method that i can invoke that tells me if a number is prime or a difficult algorithm i need to learn than so be it but i feel like putting restraints on things like this like only using what she has taught us in class is doing nothing but holding back peoples critical or out of the box thinking. just my 2 cents :P

Junilu Lacar
Sheriff
Posts: 11486
180
To be fair to OP, this is kind of an Egg of Columbus type deal. When you know the solution, it seems obvious but if you don't, it's difficult to come up with it yourself. One of the most common algorithm students will be asked to implement has been around for literally centuries and to most, it still is an interesting discovery when you learn about it.

Still, it's a good exercise to try and think through the process you'd go through to test for a number's primality. Just don't get down on yourself if you can't figure something out now because when you do learn how to do it, it will seem obvious.

Junilu Lacar
Sheriff
Posts: 11486
180
Mike, you have to let some of those frustrations go. In this particular case, I don't see anything that indicates your instructor is trying to dumb things down. I think it would have been nice if she warned you about the Egg of Columbus thing so you wouldn't feel so bad when you learned about the method that you're probably going to be asked to implement in a program but other than that, it's actually good preparation to start figuring out some of the things already discussed so far.

That said, if she gives you another skeleton program that's anything like the other one you shared before, then that's going to be whole ''nother story.

Paul Clapham
Sheriff
Posts: 22828
43
Mike Mo wrote:my thing with this whole class so far has been that i have an issue with learning "half ass" ways to do things. if there is a correct way and 5 "dumbed down" ways i would rather learn the hard way that is correct 100% of the time. my grandpa always said that the hard was is the easy way. if you get the work done now(the hard way) then later on when you want to do something, the work is done and you can do that. this makes you realize at that time that the hard was was in fact the easy way. this has proven to be true even when i didnt follow it haha hes a smart man. so i try to apply this to everything within reason in my life. so i guess in short i dont really want to have to learn a dumbed down way of doing something bc its a waste of time. if there is a method that i can invoke that tells me if a number is prime or a difficult algorithm i need to learn than so be it but i feel like putting restraints on things like this like only using what she has taught us in class is doing nothing but holding back peoples critical or out of the box thinking. just my 2 cents :P

Yeah, that's all true... for things which have only one good way to do them. Sure, the "divide by all smaller numbers up to the square root" works just fine for finding out if 2701 is prime. But if somebody gives you an insanely huge number with 1200 digits and asks you whether it's a prime, then "divide by all smaller numbers up to the square root" isn't going to finish before the universe fizzles out. However there are other ways to do it, worked out by mathematicians and computer scientists, which do work in a reasonable amount of time.

But nobody expects you to come up with that algorithm just by thinking about it for a couple of days. Especially if you didn't already get an advanced degree in math!

Besides, the "divide by all smaller numbers etc" isn't a dumbed-down way. Asking whether a number is prime is one thing. Asking what its factors are is another thing entirely. If you can do "divide by all smaller numbers etc" then you find the factors automatically as a side effect. But if you're given that insanely huge number then it's almost impossible to find its factors. Is it prime? You can find that out OK. What are its factors? Not enough time in the universe's life to find out.

And also besides, the point of this assignment isn't to teach you the way (or a way) to find out whether a number is prime. It's supposed to be a fairly simple programming goal which teaches you some basic programming tools.

Junilu Lacar
Sheriff
Posts: 11486
180
Paul Clapham wrote:And also besides, the point of this assignment isn't to teach you the way (or a way) to find out whether a number is prime. It's supposed to be a fairly simple programming goal which teaches you some basic programming tools.

That's an excellent point. When thinking about how you would do it, you also want to start thinking about what variables you'll need, their types, and the kind of flow control statements you might use to make decisions or repeat some of the steps in the process. Relate these to the things you've already learned about in your class.

Mike Mo
Ranch Hand
Posts: 40
so today in class she showed us what she was thinking when she wanted us to think about the prime number issue. she wanted us to use loops (somewhat obvious b/c of the redundancy of the task) to check each number in a chain for its "prime-ness". so for example maybe I could do something like...

so basically it would use a loop to keep track of how many factors there are for a given input. if a given age is only divisible by 1 and itself (i.e. it is prime), then the primeCount value will be 2 telling us that it is prime. I'm not sure exactly how to code this but i will work on it and see what i can come up with. the above is all i really have at the moment. any tips or comments are appreciated.

Paul Clapham
Sheriff
Posts: 22828
43
Your logic looks pretty decent. In fact it looks like it should work. One thing I'd complain about, though: you said (correctly) that you were keeping track of how many factors there are for the "age" variable. Then why would you represent the number of factors by a variable named primeCount? That's going to confuse people who look at the code. And it's even going to confuse you if you have to come back and change that code later.

Junilu Lacar
Sheriff
Posts: 11486
180
Mike Mo wrote:
... I'm not sure exactly how to code this...

Said the guy who just did.

Paul is right, that code should work and you should rename the primeCount variable to something that reflects what you just explained in your post:
Mike Mo wrote:"... keep track of how many factors there are for a given input."

If you think out loud, you'll often hear yourself saying the appropriate names you need to use in your program as you explain the solution to someone or yourself.

I always program with some buddies, even when I'm alone, so I have someone to bounce my ideas off of.

 It is sorta covered in the JavaRanch Style Guide.