# prime numbers

hi I'm trying to write code that will print out all the prime numbers between 2 and 100. I can't get it to work correctly, though. Could anyone please help me? My code is below:

public class Primes {

public int prime;

public Primes() {
}
public void isPrime(){

System.out.println("PRIMES: ");

for (int prime = 2; prime <= 100; prime++){

if ( prime%prime == 0 )
break;
else
System.out.print(prime + " ");
}
}
}
«1

• Your code is almost right. The only flaw is that you check wheter [red]prime % prime[/red] is equal to zero. It always is since prime is the same value as prime. Do you see it? Here's a modified code (note the second for-loop).

[code]
public class Temp extends JFrame
{
public static void main (String[] arg)
{
for (int i = 2; i < 100; i++)
for (int j = 2; j < i; j++)
{
if (i % j == 0)
break;
else if (i == j + 1)
System.out.print (i + " ");
}
}
}
[/code]

Kind Regards
----------------------------
(+46/0) 708-70 73 92
chamster@home.se

• In case you'd like to create a better algorithm there are some simple changes you might want to do (also some more complex, though more powerfull).

* Prime numbers up to 100 are the same as prime numbers up to square root of 100. Use [green]Math.sqrt (100)[/green] in the for-loop.

* You don't need to check even numbers (there's only one even prime number and it's 2). Use [green]i += 2[/green] as the increase for i.

* Once you've found a prime number (let's say 5), you can remove all powers of it. For that you need a boolean array and it's probably nothing you should worry about right now :-).

Kind Regards
----------------------------
(+46/0) 708-70 73 92
chamster@home.se

• : In case you'd like to create a better algorithm there are some simple changes you might want to do (also some more complex, though more powerfull).
:
: * Prime numbers up to 100 are the same as prime numbers up to square root of 100. Use [green]Math.sqrt (100)[/green] in the for-loop.
:
: * You don't need to check even numbers (there's only one even prime number and it's 2). Use [green]i += 2[/green] as the increase for i.
:
: * Once you've found a prime number (let's say 5), you can remove all powers [red][you mean multiples (though powers is technically also correct, just not as strict)][/red]of it. For that you need a boolean array and it's probably nothing you should worry about right now :-).
:
:
: Kind Regards
: ----------------------------
: (+46/0) 708-70 73 92
: chamster@home.se
:
:

"We can't do nothing and think someone else will make it right."

• : you can remove all powers [red][you mean multiples (though powers is technically also correct, just not as strict)][/red]

Are you sure? Have you tested? (Especially for large numbers :-))
It's very natural to believe that it's multiples that should be removed, but i believe it's powers. How would you argue for your theory? (Is it [b]argue[/b] or [b]argument[/b], by the way?)

Kind Regards
----------------------------
(+46/0) 708-70 73 92
chamster@home.se

• Thank you for all your help. It helped me a lot.

RodeoBurnz

: : you can remove all powers [red][you mean multiples (though powers is technically also correct, just not as strict)][/red]
:
: Are you sure? Have you tested? (Especially for large numbers :-))
: It's very natural to believe that it's multiples that should be removed, but i believe it's powers. How would you argue for your theory? (Is it [b]argue[/b] or [b]argument[/b], by the way?)
:
:
: Kind Regards
: ----------------------------
: (+46/0) 708-70 73 92
: chamster@home.se
:
:

• : Thank you for all your help. It helped me a lot.
:
: RodeoBurnz
:
: : : you can remove all powers [red][you mean multiples (though powers is technically also correct, just not as strict)][/red]
: :
: : Are you sure? Have you tested? (Especially for large numbers :-))
: : It's very natural to believe that it's multiples that should be removed, but i believe it's powers. How would you argue for your theory? (Is it [b]argue[/b] or [b]argument[/b], by the way?)
: :

I don't need to argue theory, it's true by definition. By definition a prime number has no factors (other than 1 and itself). By definition a multiple of n has n as a factor. The only multiple of n that can POSSIBLY be prime is the "first". I believe you've mistaken the words power and multiple (though I have no idea what you think multiple means in that case). Powers is also correct, but all (integral) powers of n are also multiples of n (again by definition).

"We can't do nothing and think someone else will make it right."

• I believe you missed my point. You claim that removing all multiples of a found prime number (as for, let's say, 3 it would be 6, 9, 12, 15,...) is the right way to go. As a proof you point out, very correctly, that a prime number is a number with no factors (but itself and one). Mathematically speaking it's the best solution.

What you seem to be missing is that it's not the fastest method. You will achieve a better performance if you only remove powers of a found prime number (as for 3 it would be 9, 27, 81, 343,...). If you don't believe me - try it yourself. It's specially clear for large numbers.

Can you see how come? (The answer is pretty obvious, when you think of it. Yet, it took me a while before i saw how that's possible.)

Kind Regards
----------------------------
(+46/0) 708-70 73 92
chamster@home.se

• Glad to be of help. Was it you who sent me that letter? If so - thanks. It was very nice.

Kind Regards
----------------------------
(+46/0) 708-70 73 92
chamster@home.se

• : I believe you missed my point. You claim that removing all multiples of a found prime number (as for, let's say, 3 it would be 6, 9, 12, 15,...) is the right way to go. As a proof you point out, very correctly, that a prime number is a number with no factors (but itself and one). Mathematically speaking it's the best solution.
:
: What you seem to be missing is that it's not the fastest method. You will achieve a better performance if you only remove powers of a found prime number (as for 3 it would be 9, 27, 81, 343,...). If you don't believe me - try it yourself. It's specially clear for large numbers.
:
: Can you see how come? (The answer is pretty obvious, when you think of it. Yet, it took me a while before i saw how that's possible.)
:
:

What do you do when you reach a composite number that's not a power of a prime? The first odd one is 15. That's not a power of three and not a power of five (and definitely not a power of any other prime). Do you divide it out? Then what about 3*5^50?

Anyways, if going by powers was faster (and still complete) then you wouldn't be using i+=2 you'd be using i*=2.

* Prime numbers up to 100 are the same as prime numbers up to square root of 100. Use Math.sqrt (100) in the for-loop.

Um could you reword this. It sounds like all the primes between 1 and 10 are all the primes between 1 and 100. I think you are confusing primality with factoring. For all composite numbers there must exist a factor between 2 and the sqrt of the number.

"We can't do nothing and think someone else will make it right."

• : What do you do when you reach a composite number that's not a power of a prime? The first odd one is 15. That's not a power of three and not a power of five (and definitely not a power of any other prime). Do you divide it out?

The first one is actually 6, not 15. And no, i don't divide that out since that isn't a power of any integer.

: Anyways, if going by powers was faster...

It [b]is[/b] faster. Since you're opposing to that i'll have to assume that you didn't follow my advice about testing it.

Your deduction about removing multiples is correct but you missed to proof that it's the fastest one (which it isn't). You seem to have assumed that.

I'll be happy to explain to you (well, everybody reading this thread, actually) what the advance with power-method is compared to multiple-method. But first i'd like you to "see" it for yourself. Write the code and test it, it only takes ten minutes.

Kind Regards
----------------------------
(+46/0) 708-70 73 92
chamster@home.se

• : : Prime numbers up to 100 are the same as prime numbers up to square root of 100. Use Math.sqrt (100) in the for-loop.
:
: Um could you reword this. It sounds like all the primes between 1 and 10 are all the primes between 1 and 100. I think you are confusing primality with factoring.

Rewording:
In order to show that 100 is/is not a prime -> show that it is/is not dividable by any prime higher than 1 and lower than 100. Now, one need only test primes up to square root of 100.

That (your quotation) was a "little" bit unclear. I blame my english and appologize for the misstake, at the same time thanking you for the notation.

The other issue (power removal) remains unchanged, though :-).

Kind Regards
----------------------------
(+46/0) 708-70 73 92
chamster@home.se

• [b][red]This message was edited by Darius at 2002-9-28 22:6:6[/red][/b][hr]
: : What do you do when you reach a composite number that's not a power of a prime? The first odd one is 15. That's not a power of three and not a power of five (and definitely not a power of any other prime). Do you divide it out?
:
: The first one is actually 6, not 15. And no, i don't divide that out since that isn't a power of any integer.

[blue]
6 isn't odd. Read my response closer.[/blue]

:
: : Anyways, if going by powers was faster...
:
: It [b]is[/b] faster. Since you're opposing to that i'll have to assume that you didn't follow my advice about testing it.
:
: Your deduction about removing multiples is correct but you missed to proof that it's the fastest one (which it isn't). You seem to have assumed that.
:
: I'll be happy to explain to you (well, everybody reading this thread, actually) what the advance with power-method is compared to multiple-method. But first i'd like you to "see" it for yourself. Write the code and test it, it only takes ten minutes.
:
[blue]
I can't test it, I don't know what your algorithm is. I don't know what to do when I have 15. It's not a power of 2, 3, 5, 7, 11, 13. Does that mean it's prime?

Finally, I think you're missing the point here's a quote from the original post.

"write code that will print out _all_ the prime numbers between 2 and 100" - emphasis added

I don't care if your code is the fastest method for testing that A number is prime (which if you don't mind a very miniscule probability that the number may actually not be prime the probabilistic methods will slaughter your implementation), is it the fastest to find ALL prime numbers?

Part of the problem with your original note about the sqrt of 100 was simply the wording, another part was the fact that you were solving a different problem. You ARE doing factoring (only instead to tell if there ISN'T a factor). I must say that my response is poorly worded now that I think of it, that WILL be fine for primality TESTING, but it's less efficient for simply FINDING primes. As that would mean using your primality TESTING algorithm for every natural number or the optimization of every odd natural number >2. Of course, the fact that that's an optimization and that's equivalent to removing multiples of two, suggests that further optimizing by say removing multiples of three would be faster, and continuing that you eventually squeeze out the necessity of even testing the numbers as you will effectively be filtering out ALL composite numbers.[/blue]

"We can't do nothing and think someone else will make it right."

• : 6 isn't odd. Read my response closer.

Odd means "not-even" but also "not-usual" or "not-standard". Hence 6 is the first odd number meaning a number that can't be removed by power-method.

: I can't test it, I don't know what your algorithm is. I don't know what to do when I have 15. It's not a power of 2, 3, 5, 7, 11, 13. Does that mean it's prime?

Of course it's not. You just test 15 and already at 3 it will be proven non-prime. And please, writing the code takes a couple of minutes. I can even [b]give[/b] you the code...

: "write code that will print out _all_ the prime numbers between 2 and 100" - emphasis added

: I don't care if your code is the fastest method for testing that A number is prime (which if you don't mind a very miniscule probability that the number may actually not be prime the probabilistic methods will slaughter your implementation), is it the fastest to find ALL prime numbers?

I do (in this case) mind any, even a "very miniscule probability" chanse of getting an error (consider the level of complexitiy required by the original poster, which is pretty low, i'd say).
And frankly, Darius, you make me disappointed when saying that you don't care about speed of a method. [grey]Parhaps you should stick to proof-reading my english, rather than commenting my code... (This one was nasty, i admit. Try to see the humour in this as i mean it only partially.)[/grey]

: you were solving a different problem.

I was giving extra tips about further methods, not solving anything. Perhaps i should have mentioned even more complex methods but frankly, i thought the power-method is a little overkill for somebody who wants to get primes up to 100, so i just let that be.

: You ARE doing factoring.

Is there an other way to solve this exactly? Please let me know.

: ...that's equivalent to removing multiples of two, suggests that further optimizing by say removing multiples of three would be faster...

You just don't get it, do you. I'm not going deeper into this "it's too, it's not"-discussion with you. Specially that you didn't even bothered to test wheter what you [b]think/assume[/b] to be true, really is. I get a student like that every year (except this year, since i'm free of work). I got the impression of you being a heavy-asset to all members of this forum. Having a little God-complex, are we? :-) (You know - "nobody can teach me anything new"-attitude)

I hope you'll regard it as something to learn from not to be angry about.

Kind Regards
----------------------------
(+46/0) 708-70 73 92
chamster@home.se

• : : 6 isn't odd. Read my response closer.
:
: Odd means "not-even" but also "not-usual" or "not-standard". Hence 6 is the first odd number meaning a number that can't be removed by power-method.

Given the context this is somewhat ridiculous.

:
: : I can't test it, I don't know what your algorithm is. I don't know what to do when I have 15. It's not a power of 2, 3, 5, 7, 11, 13. Does that mean it's prime?
:
: Of course it's not. You just test 15 and already at 3 it will be proven non-prime. And please, writing the code takes a couple of minutes. I can even [b]give[/b] you the code...

If I need to test the remaining numbers with my own algorithm, what has your algorithm given me? A) It becomes clear why I can't implement your algorithm, it doesn't return primes and you haven't told me how to post-process the numbers I get. If I use the naive algorithm for primality testing on each number I get from your method (and don't argue that I shouldn't, if one were asking for a fast prime finding algorithm, then likely one wouldn't already know a fast primality testing algorithm) then the running time would be dominated by the naive algorithm. Some points: as the numbers got higher the gaps between powers would become larger, resulting in even more numbers needing to be tested by a user supplied algorithm (in this case the naive algorithm) and those numbers would be, well, larger and require more time by the user supplied algorithm.

Finally, it was ridiculous to state "already at 3, 15 will be proven composite". I could have given 1330133837 as an example that is also not caught by your algorithm, is definitely composite, and you won't be finding a factor of it, "already", before 30,000, however this number would be handled by sieving by multiples and sieving by multiples would require no algorithm to post-process the data.

:
: : "write code that will print out _all_ the prime numbers between 2 and 100" - emphasis added
:
: : I don't care if your code is the fastest method for testing that A number is prime (which if you don't mind a very miniscule probability that the number may actually not be prime the probabilistic methods will slaughter your implementation), is it the fastest to find ALL prime numbers?
:
: I do (in this case) mind any, even a "very miniscule probability"

(As a sidenote then: I hope you've examined the source code of any encryption/privacy software you use then. Your private key could quite possibly be generated via probablistic methods. Also, in this case, there's an arbitrarily more likely case in which you get a composite simply due to a hardware glitch.)

chanse of getting an error (consider the level of complexitiy required by the original poster, which is pretty low, i'd say).
: And frankly, Darius, you make me disappointed when saying that you don't care about speed of a method.

Read the whole paragraph at once. I said I don't care about the speed of a method to get _A_ prime as the problem is to get _ALL_ primes. This is equivalent to me saying, "I don't care about the speed of a method to solve quadratic equations, I'm making a search routine." Also, you didn't answer my final question, is it fastest to find ALL prime numbers?

:
: : you were solving a different problem.
:
: I was giving extra tips about further methods, not solving anything. Perhaps i should have mentioned even more complex methods but frankly, i thought the power-method is a little overkill for somebody who wants to get primes up to 100, so i just let that be.

My point is that you were mentioning "further methods" for a different problem. Getting primes up to 100 is not the same problem as finding whether 100 is prime.

:
: : You ARE doing factoring.
:
: Is there an other way to solve this exactly? Please let me know.

There are ways to incrementally invalidate composite numbers so that you are simply left with prime numbers.

:
: : ...that's equivalent to removing multiples of two, suggests that further optimizing by say removing multiples of three would be faster...
:
: You just don't get it, do you. I'm not going deeper into this "it's too, it's not"-discussion with you. Specially that you didn't even bothered to test wheter what you [b]think/assume[/b] to be true,

I said, I didn't test it because I can't. Your algorithm isn't fully specified. I haven't said you were wrong, I just haven't accepted that you were right and have pointed out that your algorithm alone doesn't result in primes and you haven't specified how to complete it so that it will. You haven't qualified that your algorithm is faster except by saying, try it and find out. You continue to say that even after I said I can't try it without knowing what it is. I seriously hope your students don't accept without question what you say, just as they shouldn't accept without question what they read, or anything else. The goal of the student is to question everything. Judging by your ad hominem and irrelevant remarks to the legitimate concerns and questions I've posed as well as the purposeful or accidental misinterpretations of what I've said and what can only be purposeful misrepresentations of what I've said, I'm led to believe that some of your "know-it-all" students may merely be students that are _trying_ to know it all.

Finally, as there are no language barriers or ambiguities or room for incompleteness in code, I WOULD like you to provide an example program using your algorithm. Preferably allowing a user-defined and/or potentially infinite (within the bounds of the machine) upper-bound.

"We can't do nothing and think someone else will make it right."

• : Given the context this is somewhat ridiculous.

No it's not. You expressed your thought in such manner that somebody missinterpreted it (and please don't say "well, you wanted to").

: : Of course it's not. You just test 15 and already at 3 it will be proven non-prime. And please, writing the code takes a couple of minutes. I can even [b]give[/b] you the code...

: If I need to test the remaining numbers with my own algorithm, what has your algorithm given me?

If you by "my own algorithm" mean "removal of multiplicities" (ROM)then the answer is "nothing" since i won't be using ROM at all. If you by "my own algorithm" mean "statistical estimation" (SE) then the answer is "nothing" since i won't be using SE at all either.

The point with the algoritm is to treat all numbers as potential primes unless found being a power of an (already found/proven) prime. What an untrained eye fails to see is that "being a power of" is actually faster then "being a multiplicity of". The motivation is usualy that ROM "misses numbers" and/or "makes unneeded checking" (which is, as i understand, what you believe).

: : I do (in this case) mind any, even a "very miniscule probability"
: ...I hope you've examined the source code of any encryption/privacy software you use then.

Yes, i did. And i still mind. If you know that you will have x attempts to find the key and probability of success is 1 to x^1000 then i:
a) do mind since it's still insecure in theory (i wouldn't bet my life on it)
b) do not care since it's secure in practice (i would, and do, use e-banking)
You mention SE, you mention internet security problems and that's fine. Yet, what we disagree about (and what you still fail to see/believe/try/understand) is that ROM is slower than ROP (just so we don't loose focus of "our" issue). Since only one of us can be right i want:
a) to proof you wrong or
b) make you proof me wrong (at which point i'll gladely reevaluate my position and be able to do a) to somebody else
I call that process [b]learning by nagging[/b] :-)...

: I said I don't care about...

OK, i see your point there. (less disappointed :-))

: Also, you didn't answer my final question, is it fastest to find ALL prime numbers?

Sorry, i thought you ment that question to be rethorical since:

There's no such thing as finding "ALL prime numbers" since they're always "one to many" (if you regard the proof of infinity of primes).

If you ment "ALL prime numbers within given limits" then no. The fastest method would be "having an array with all prime numbers within givin limits" (and that's of course trivial).

That said, i believe ROP is fairly (how do i define "fairly"? :-)) fast but if you've got some other kind of approach i'll be extatic to get to know it (the shorter the better, like, under 100 lines or so). What i [b]do know[/b] is that ROM is not.

: Getting primes up to 100 is not the same problem as finding whether 100 is prime.

Well, philosophically speaking you could regard the one as a part of the other. But i see your point there.

: There are ways to incrementally invalidate composite numbers so that you are simply left with prime numbers.

Do you mean like defining a bool[] assuming all positions to be true (where every position's number corresponds to an integer) and then making some of them false if found not-prime? That [b]is indeed[/b] the method i suggested (and it can be done both with ROM and ROP, allthough ROP is faster).

: Your algorithm isn't fully specified.

OK, i get it. I assume(d) that you have an algorithm (pretty much any*) that uses ROM. Change the ROM to ROP and test the times. I get about 5% faster times for range 1 to 1'000'000.
*[grey]For simplicity of the code (so that changes are smallest possible) test every number, not only the odd ones.[/grey]

: I haven't said you were wrong, I just haven't accepted that you were right...

Yes you did. You didn't say "...or also one might use multiplicities". You said "no, you can't use powers; you must use multipicities".

: You haven't qualified that your algorithm is faster except by saying, try it and find out.

That's correct. I didn't want to spoil the fun of
a) you seeing that yourself (i was told the solution which deprived me of getting to it myself)
b) teasing you a little bit (and i'm sorry if i caused you irritation).

: I seriously hope your students don't accept without question what you say... The goal of the student is to question everything.

Some do. The smart ones don't. This is the best part of teaching, actually - leading the lions, not the sheep!

I posted a tip (ROP) that you failed to understand. You corrected it and i opposed. Is that your definition of "ad hominem"? And no, i don't try to missinterpret what you say. I really did missinterpret. Has it occure to you that you [b]might[/b] be a little unclear, since you (perhaps) were irritated?

By the way - personal assault - has never been my intention. I question what you say, not yourself. If you feel so - i appologize.

: some of your "know-it-all" students may merely be students that are _trying_ to know it all.

Yes, the "sheepy-ones". They try, and they fail.

: Finally, as there are no language barriers or ambiguities or room for incompleteness in code, I WOULD like you to provide an example program using your algorithm. Preferably allowing a user-defined and/or potentially infinite (within the bounds of the machine) upper-bound.

That should be arrangable. Of course, i don't think you'll need it now, since i have (i hope) explained how to create the algorithm from your own creation. If you for some reason can't manage to make that changes yourself, post the code and i'll show you exactly what to do. (As the last source i can post an example myself but as i mentioned before, i don't want to spoil the fun for you.)

Kind Regards