Java

Java RSS

Help to find prime numbers without using an array

Please support our Java advertiser: Programming Forums - DaniWeb Sister Site

•

Join Date: Oct 2007

Posts: 2

Reputation: nucleareactr is an unknown quantity at this point

Solved Threads: 0

nucleareactr nucleareactr is offline

Offline

Newbie Poster

Help to find prime numbers without using an array

Oct 30th, 2007

Hey all,

In computer class as homework we're to create a code to find prime numbers between two values m and n without using an array (since we havn't learned about how to use them yet).

so far the code I have is:

 Help with Code Tags 
 Java Syntax (Toggle Plain Text) 
  public static void prime (int m, double n){
    int prime = m;
    while (prime <= n){
      if(isPrime(prime)){
        System.out.print(prime+", "); 
      }
      prime ++;
    }
  }
 
  public static boolean isPrime (int p){
      for (int x = 2; x < p; x++){
        if (p%x == 0){
          return false;
        }
      }
      return true;
  }
  public static void prime (int m, double n){
    int prime = m;
    while (prime <= n){
      if(isPrime(prime)){
        System.out.print(prime+", "); 
      }
      prime ++;
    }
  }

  public static boolean isPrime (int p){
      for (int x = 2; x < p; x++){
        if (p%x == 0){
          return false;
        }
      }
      return true;
  }

This are the two methods - prime and isPrime - I created to find the prime numbers between the two numbers m and n. The program works fine, however if m = 10 and n = 10000, the program takes a very long time to print out all the prime numbers inbetween 10 and 10000. I would like to shorten this time. I assume this is because of the for loop inside the isPrime method. Hopefully someone will be able to help me here since I have been struggling with this problem for quite some time.

Thanks

•

Join Date: May 2007

Posts: 4,483

Reputation: Ezzaral has much to be proud of

Solved Threads: 515

Ezzaral

Offline

Industrious Poster

Re: Help to find prime numbers without using an array

Oct 30th, 2007

Well, you probably don't want to get into the more esoteric algorithms for finding primes, but there are a few simple modifications that will reduce the number of checks you have to make.
If p%2==0, it's prime.
If that is not the case, you can start the loop at 3 and increment by 2 for each iteration. You don't need to check any other even numbers.
Your loop also doesn't need to check any higher than sqrt(p).

Maybe that helps a bit.

(I'm assuming you don't need to accomodate the check for p=1)

Last edited by Ezzaral; Oct 30th, 2007 at 8:18 pm.

•

Join Date: Oct 2007

Posts: 2

Reputation: nucleareactr is an unknown quantity at this point

Solved Threads: 0

nucleareactr nucleareactr is offline

Offline

Newbie Poster

Re: Help to find prime numbers without using an array

Oct 30th, 2007

Wow that really makes sense. Thank you so much for the help. The only clarification that I need is that for

Help with Code Tags

Java Syntax (Toggle Plain Text)

 sqrt(p)

, where is that applied? Is it at the part where it says

 Help with Code Tags 
 Java Syntax (Toggle Plain Text) 
 for (int x = 2; x < p; x++)
 for (int x = 2; x < p; x++)

?

Thanks

Last edited by nucleareactr; Oct 30th, 2007 at 11:06 pm. Reason: Clarification

•

Join Date: May 2007

Posts: 4,483

Reputation: Ezzaral has much to be proud of

Solved Threads: 515

Ezzaral

Offline

Industrious Poster

Re: Help to find prime numbers without using an array

Oct 31st, 2007

•

Originally Posted by nucleareactr

Wow that really makes sense. Thank you so much for the help. The only clarification that I need is that for
Help with Code Tags

Java Syntax (Toggle Plain Text)
 sqrt(p)
sqrt(p)
, where is that applied? Is it at the part where it says
Help with Code Tags

Java Syntax (Toggle Plain Text)
 for (int x = 2; x < p; x++)
for (int x = 2; x < p; x++)
?

Thanks

Yes, your prime check doesn't need to check numbers greater than the square root of the number. Any product greater than the number times itself will involve a factor less than the number itself, which you have already checked.