471,887 Members | 1,421 Online

Prime number generator

I am new to Java and programming, I have an assignment that I am a little stuck on and I was hoping to get a little help if anyone is willing. I have read a few posts on the topic and it seems most people on here want to see where you've gotten and then give a little help to get past roadblocks, so here goes.

My program should accept an integer and then print out the primes between 0 and that number, so my idea is to start a for loop that increments one at a time and then checks it for primality and prints it if its prime, until it gets to the input integer the problem is that I can't find a test for primality that doesn't have a built in list. any suggestions??
Feb 6 '08 #1
15 6379
Laharl
849 Expert 512MB
What is the definition of a prime number? In other words, what is a simple test that will immediately disqualify any number as prime?
Feb 6 '08 #2
1,216 Expert 1GB
Was there any discussion or hints given with your assignment? There's a classic algorithm to find all the primes less than a given limit N, but I don't want imply you have to solve it that way.
Feb 6 '08 #3
r035198x
13,262 8TB
... the problem is that I can't find a test for primality that doesn't have a built in list. any suggestions??
I'm sorry but I don't understand the part above.
You could have a look at BigInteger.isProbablePrime but perhaps your teachers won't accept it.
Feb 6 '08 #4
1,216 Expert 1GB
I'm sorry but I don't understand the part above.
You could have a look at BigInteger.isProbablePrime but perhaps your teachers won't accept it.
Ah, industry-grade primes! No, I think the teacher wouldn't be impressed. It seems to be the point of the exercise.
Feb 6 '08 #5
Well, I was just going with my math class difinition, the assignment was a little vauge, but it did say no built in methods or arrays, so the conditions that I uderstand for a prime are that a number is prime if and only if it is divisible by one and itself. I had thought about trying to inverse that to create a limiting conditon but how??
Feb 6 '08 #6
664 Expert 512MB
Well, I was just going with my math class difinition, the assignment was a little vauge, but it did say no built in methods or arrays, so the conditions that I uderstand for a prime are that a number is prime if and only if it is divisible by one and itself. I had thought about trying to inverse that to create a limiting conditon but how??
I would not inverse it just use a + counter.
I would use a for loop with a
Integer.parseInt();

Feb 6 '08 #7
1,216 Expert 1GB
Well, I was just going with my math class difinition, the assignment was a little vauge, but it did say no built in methods or arrays, so the conditions that I uderstand for a prime are that a number is prime if and only if it is divisible by one and itself. I had thought about trying to inverse that to create a limiting conditon but how??
No arrays? There goes my choice: the Sieve of Eratosthenes. There's a very cool animated gif of the algorithm on that page, by the way.

I don't know what you mean by "trying to inverse that to create a limiting conditon". I think you are over-thinking. Why not try the old "understand how you do it manually" approach? How would you determine whether or not 91 was prime? Do this in deliberate steps.
Feb 6 '08 #8
r035198x
13,262 8TB
No arrays? There goes my choice: the Sieve of Eratosthenes. There's a very cool animated gif of the algorithm on that page, by the way.

I don't know what you mean by "trying to inverse that to create a limiting conditon". I think you are over-thinking. Why not try the old "understand how you do it manually" approach? How would you determine whether or not 91 was prime? Do this in deliberate steps.
Ah, that sieve again. I was hoping no one would bring that one up.
Feb 6 '08 #9
664 Expert 512MB
No arrays? There goes my choice: the Sieve of Eratosthenes. There's a very cool animated gif of the algorithm on that page, by the way.

I don't know what you mean by "trying to inverse that to create a limiting conditon". I think you are over-thinking. Why not try the old "understand how you do it manually" approach? How would you determine whether or not 91 was prime? Do this in deliberate steps.
was mjslaugh thinking of a negative counter?
Feb 6 '08 #10
1,216 Expert 1GB
Done. And done. And done.
Feb 6 '08 #11
r035198x
13,262 8TB
was mjslaugh thinking of a negative counter?
No he was talking about reversing the "divisible by 1 and itself part" to finding any number other that 1 and itself that divides into the given number. Which will work for him.
Feb 6 '08 #12
jkmyoung
2,057 Expert 2GB
Are you allowed to store your results as you get them?

It would be a dynamic array created as your program ran, not a 'built-in array'.
Then you could check whether your current number is divisible by any of the smaller primes, up to it's square root.
Feb 6 '08 #13
1,216 Expert 1GB
Are you allowed to store your results as you get them?

It would be a dynamic array created as your program ran, not a 'built-in array'.
Then you could check whether your current number is divisible by any of the smaller primes, up to it's square root.
I'm not a mind reader, but if the teacher forbade arrays, I can't imagine in my wildest dreams that he'd be glad to see a list in its place!
Feb 6 '08 #14
This is the structure that I have so far. You can see what boolean condition that I am missing.

inInt = kb.nextInt();

for(int x = 0; x < inInt; x++){

if( )\\not prime
else
System.out.print(x + " ");

The problem is that I can't figure out how to rule out if a number is prime other than checking divisibility of several numbers. Or should I embrace that idea and write a method that returns the boolean condition based on dividing several numbers?? I really apreciate the help everyone.
Feb 6 '08 #15
Nepomuk
3,112 Expert 2GB
This is the structure that I have so far. You can see what boolean condition that I am missing.

inInt = kb.nextInt();

for(int x = 0; x < inInt; x++){

if( )\\not prime
else
System.out.print(x + " ");
Well, the loop looks a bit weird, but I guess that's just because it's incomplete.
The problem is that I can't figure out how to rule out if a number is prime other than checking divisibility of several numbers. Or should I embrace that idea and write a method that returns the boolean condition based on dividing several numbers??
Sound's like it will work, doesn't it? And you can limit the amount of numbers, through which you divide... just think about it. :-)

Greetings,
Nepomuk
Feb 6 '08 #16