Help to find prime numbers without using an array
 

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:

  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

Re: Help to find prime numbers without using an array
 

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)

Re: Help to find prime numbers without using an array
 

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

 sqrt(p)

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

 for (int x = 2; x < p; x++)

?

Thanks

Re: Help to find prime numbers without using an array
 

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.