Prime number generator

[mjslaugh]

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??

[Laharl]

What is the definition of a prime number? In other words, what is a simple test that will immediately disqualify any number as prime?

[BigDaddyLH]

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.

[r035198x]

... 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.

[BigDaddyLH]

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.

[mjslaugh]

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??

[nomad]

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();

nomad

[BigDaddyLH]

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.

[r035198x]

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.
@SmallDaddy: Check your PMs please.

[nomad]

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?
nomad

[BigDaddyLH]

@SmallDaddy: Check your PMs please.

Done. And done. And done.

[r035198x]

was mjslaugh thinking of a negative counter?
nomad

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.

[jkmyoung]

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.

[BigDaddyLH]

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!

[mjslaugh]

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.

[Nepomuk]

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