Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

prime numbers

RodeoBurnzRodeoBurnz Member Posts: 47
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 + " ");
}
}
}
«13

Comments

  • chamsterchamster Member Posts: 662
    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
    Konrad
    ----------------------------
    (+46/0) 708-70 73 92
    chamster@home.se
    http://konrads.webbsida.com

  • chamsterchamster Member Posts: 662
    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
    Konrad
    ----------------------------
    (+46/0) 708-70 73 92
    chamster@home.se
    http://konrads.webbsida.com

  • DariusDarius Member Posts: 1,666
    : 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
    : Konrad
    : ----------------------------
    : (+46/0) 708-70 73 92
    : chamster@home.se
    : http://konrads.webbsida.com
    :
    :


    "We can't do nothing and think someone else will make it right."
    -Kyoto Now, Bad Religion

  • chamsterchamster Member Posts: 662
    : 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
    Konrad
    ----------------------------
    (+46/0) 708-70 73 92
    chamster@home.se
    http://konrads.webbsida.com

  • RodeoBurnzRodeoBurnz Member Posts: 47
    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
    : Konrad
    : ----------------------------
    : (+46/0) 708-70 73 92
    : chamster@home.se
    : http://konrads.webbsida.com
    :
    :

  • DariusDarius Member Posts: 1,666
    : 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."
    -Kyoto Now, Bad Religion

  • chamsterchamster Member Posts: 662
    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
    Konrad
    ----------------------------
    (+46/0) 708-70 73 92
    chamster@home.se
    http://konrads.webbsida.com

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


    Kind Regards
    Konrad
    ----------------------------
    (+46/0) 708-70 73 92
    chamster@home.se
    http://konrads.webbsida.com

  • DariusDarius Member Posts: 1,666
    : 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."
    -Kyoto Now, Bad Religion

  • chamsterchamster Member Posts: 662
    : 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
    Konrad
    ----------------------------
    (+46/0) 708-70 73 92
    chamster@home.se
    http://konrads.webbsida.com

«13
Sign In or Register to comment.