This discussion is archived
1 2 Previous Next 23 Replies Latest reply: Nov 6, 2010 4:38 PM by 800147 RSS

Finding a prime number

800147 Newbie
Currently Being Moderated
Hi,

I am supposed to make a program that displays a prime number in the range 1 to number.

I made it for the range 3 to number.
static void prime ( int number ){
          
          for(int i = 3; i <= number; i++){
          int r = 0;
          for( int j = 2; j <= i - 1; j++){
                    r = i % j;
                    if( r == 0 ) {
                       break;
                    }
                    else
                       r = i % j;
          }
          if( r != 0 )
               System.out.println(i + " is prime");
           
          }
}
Any ideas how to incorporate values 1 and 2?

Thanks in advance.
  • 1. Re: Finding a prime number
    804650 Journeyer
    Currently Being Moderated
    Since 1 is not prime and 2 is, you could just cheat and have two separate print statements for them before going into the loop for the rest of the numbers.
  • 2. Re: Finding a prime number
    800147 Newbie
    Currently Being Moderated
    Pinto wrote:
    Since 1 is not prime and 2 is, you could just cheat and have two separate print statements for them before going into the loop for the rest of the numbers.
    :) Absolutely, but I was thinking if I can actually put them in the calculations somehow. But maybe it'll be just easier with the print statements.
  • 3. Re: Finding a prime number
    804650 Journeyer
    Currently Being Moderated
    You can definately change your code to handle 2 but 1 is a special case. Even though it doesn't have any divisors it is still not considered prime.
  • 4. Re: Finding a prime number
    EJP Guru
    Currently Being Moderated
    j <= i - 1
    You can make it many times as fast by changing that to:
    j*j < i
    Do you understand why?
  • 5. Re: Finding a prime number
    804650 Journeyer
    Currently Being Moderated
    EJP wrote:
    j <= i - 1
    You can make it many times as fast by changing that to:
    j*j < i
    Do you understand why?
    That fails for 3. Better and more common approach is j less than or equal to square root of i
  • 6. Re: Finding a prime number
    804650 Journeyer
    Currently Being Moderated
    Hehe

    The square root method also fails for 3 due to how OP has written the code.
  • 7. Re: Finding a prime number
    EJP Guru
    Currently Being Moderated
    Better and more common approach is j less than or equal to square root of i
    Please explain analytically the difference between
    j*j <  i
    and
    j < Math.sqrt(i)
    and please enumerate one or more cases for which they yield different results.
  • 8. Re: Finding a prime number
    804650 Journeyer
    Currently Being Moderated
    Yeah yeah yeah

    I was momentarily blinded by the fact that it didn't work until I realised it was the algorithm at fault.
  • 9. Re: Finding a prime number
    EJP Guru
    Currently Being Moderated
    Precisely. I note also that evaluating j*j is several times as fast as evaluating the square root of i.

    There is also no point whatsoever in the OP's 'else' block.
  • 10. Re: Finding a prime number
    800147 Newbie
    Currently Being Moderated
    EJP wrote:
    j <= i - 1
    You can make it many times as fast by changing that to:
    j*j < i
    Do you understand why?
    No. Can you, please explain?
  • 11. Re: Finding a prime number
    796440 Guru
    Currently Being Moderated
    blias wrote:
    EJP wrote:
    j <= i - 1
    You can make it many times as fast by changing that to:
    j*j < i
    Do you understand why?
    No. Can you, please explain?
    I want to find the factors of 36:
       1  2  3  4  6  9  12 18 36
    x
      36 18 12  9  6  4  3  2 1
    See how once I hit 6--that is, the square root of 36--everything starts repeating? By the time I hit the sqrt, I have found all the factors. So by the time I hit the sqrt of some number, if I haven't found any factors other than that number and 1, there aren't any, so it's prime.

    So, if you want to know if 100,000,007 is prime, would you rather iterate through 100 million values, or 10 thousand?

    Edited by: jverd on Nov 5, 2010 11:27 AM
  • 12. Re: Finding a prime number
    800147 Newbie
    Currently Being Moderated
    Thanks for the great explanation, jverd. I understand it.

    Since I am still unable to incorporate the algorithm into my code I've decided to try to put your explanation into a code that finds the factors (as first step). Hopefully I'll get better understanding once I get it working.
    static void factors ( int number ){
              
              StringBuilder sb = new StringBuilder();
              StringBuilder sb1 = new StringBuilder();
              int r = 0;
              
              for( int i = 1; i < Math.sqrt(number); i++){
                   if(number % i == 0){
                        r = number / i;
                        if( sb.length() != 0 )
                             sb.insert(sb.length(), " ,");
                        sb.insert(sb.length(), r);
                        if( sb1.length() != 0 )
                             sb1.insert(sb1.length(), " ,");
                        sb1.insert(sb1.length(), i);
                   }
              }
              
              System.out.println(number + " has factors " + sb + " ," + sb1);
                             
         }
    If I get 36 as an example the program misses the sqrt value itself. I understand it is because
    for( int i = 1; i < Math.sqrt(number); i++)
    but if I change
    i <= Math.sqrt(number; 
    I get the value displayed twice.

    Any hints?
  • 13. Re: Finding a prime number
    803795 Explorer
    Currently Being Moderated
    Just wondering what would happen if someone entered a negative number such as -5. Is that considered a prime number? what would your code produce?
  • 14. Re: Finding a prime number
    796440 Guru
    Currently Being Moderated
    First, rather than
    i < Math.sqrt(number)
    I recommend you follow EJP's suggestion and use
    i * i <= number
    That will be faster, and keep you in the realm of integers. (Though it will mean you'll have a smaller range you can work with before you have to upgrade to long or BigInteger).

    As for duplicating the sqrt, I hope you see why it's happening. You're appending both factors, and in the case of the sqrt, both factors are the same. Just add a simple if test for i * i != number or i != r before doing the second append.

    A couple additional points:

    1) Rather than sb.insert(sb.length(), X), simply do sb.append(X).

    2) You only need the length() != 0 test when appending r. By the time you get to appending i, you've always already appended r, so the length can't be zero.
1 2 Previous Next

Legend

  • Correct Answers - 10 points
  • Helpful Answers - 5 points