Ad:

Java Discussion Thread
Unsolved
Views: 15027

Oct 30th, 2007

Help to find prime numbers without using an array

Expand Post »

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:

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

Similar Threads

prime numbers in C++
C++ prime numbers in C++
Finding Prime numbers without using Boolean in C++
how do u find prime numbers in an array in C
prime numbers in C++

nucleareactr

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

2 posts
since Oct 2007

Permalink

Oct 30th, 2007

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)

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

Ezzaral

Moderator

Featured Poster

Reputation Points: 3239

Solved Threads: 839

Posting Genius

Offline

6,761 posts
since May 2007

Permalink

Oct 30th, 2007

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

Java Syntax (Toggle Plain Text)

 sqrt(p)

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

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

nucleareactr

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

2 posts
since Oct 2007

Permalink

Oct 31st, 2007

Re: Help to find prime numbers without using an array

Click to Expand / Collapse Quote 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
Java Syntax (Toggle Plain Text)
 sqrt(p)
sqrt(p)
, where is that applied? Is it at the part where it says
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.

Ezzaral

Moderator

Featured Poster

Reputation Points: 3239

Solved Threads: 839

Posting Genius

Offline

6,761 posts
since May 2007

Permalink

Mar 5th, 2010

-1

Re: Help to find prime numbers without using an array

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

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

2 posts
since Mar 2010

Permalink

Mar 5th, 2010

Re: Help to find prime numbers without using an array

can anyone help me with this code in netbeans IDE

hussein87

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

2 posts
since Mar 2010

Permalink

Mar 5th, 2010

Re: Help to find prime numbers without using an array

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

jamesonh20

Reputation Points: 22

Solved Threads: 6

Junior Poster in Training

Offline

66 posts
since Dec 2009

Permalink

Mar 5th, 2010

Re: Help to find prime numbers without using an array

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.

Ezzaral

Moderator

Featured Poster

Reputation Points: 3239

Solved Threads: 839

Posting Genius

Offline

6,761 posts
since May 2007

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

This thread is currently closed and is not accepting any new replies.

Previous Thread in Java Forum Timeline: Conversion from java code to javaFX script

Next Thread in Java Forum Timeline: error with boolean return type

DaniWeb Message

Cancel Changes

User Name
Password