Help to find prime numbers without using an array

[nucleareactr]

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

[Ezzaral]

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)

[nucleareactr]

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

[Ezzaral]

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.

[hussein87]

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]

can anyone help me with this code in netbeans IDE

[jamesonh20]

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

[Ezzaral]

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.