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

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)

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

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

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.

1. Write a program that will be able to calculate and output all primary numbers <= a given n.
2. Analyze your program and find the Big-O notation for it.
3. Tel your opinion about the efficiency of your program.
4. What data structures have you used in your program?

hussein87 you need to post your hw prob in its own thread...ALONG WITH YOUR CODE to get any kind of help.

Yes, this thread is old and dead... but since someone pointed out to me a mistake in my post above, I'll address the mistake.

If p==2 , p is prime, for p!=2 if p%2==0 then it's not prime.
Just wanted to clear that up.

This article has been dead for over six months. Start a new discussion instead.