5 Replies - 260 Views - Last Post: 04 May 2013 - 02:45 PM Rate Topic: -----

#1 CSatVTftw  Icon User is offline

  • New D.I.C Head

Reputation: 4
  • View blog
  • Posts: 42
  • Joined: 16-April 13

PE#7 finding the 10,001 prime number

Posted 02 May 2013 - 04:13 PM

So I have code that (in my mind) should work. I'm not sure what's missing. It's getting up to 104009, which is the 9935th prime. It's looping all the way to 10002, so I'm thinking I missed something in my isPrime? TIA.

   public class PE7 {
      public static void main(String[] args) {
         int count = 0;
         int num = 0;
         while(count<=10001) {
            num++;
            if(isPrime(num)==true) {
               count++;
            }
         }
         System.out.println(num);
      }
      public static boolean isPrime(long num){
         boolean isPrimeFlag = true;
         int i = 2;
         while(i<Math.sqrt(num)) {
            if(num%i==0) {
               isPrimeFlag = false;
               break;
            }
            i++;
         }
         return isPrimeFlag;
      }
   
   }



 ----jGRASP exec: java PE7
104009

 ----jGRASP: operation complete.



Is This A Good Question/Topic? 0
  • +

Replies To: PE#7 finding the 10,001 prime number

#2 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8328
  • View blog
  • Posts: 31,857
  • Joined: 06-March 08

Re: PE#7 finding the 10,001 prime number

Posted 02 May 2013 - 05:06 PM

And what is your question ?
Beside really but really inefficient code what is your problem
I have seen horrible code computing prime numbers but you are one of the worst one

Do you realize then while testing num = 12345

doing

while(i<Math.sqrt(num)) {

will compute Math.sqrt() which is probaly a costly operation 12345 times ?
You are owner of a company selling CPUs or what ?
Compute that sqrt() only once for God love ad store it in a temp variable !!!

and why repeating the previous calculations ?

also the i++ is ridiculous... why checking all even numbers ?
should start with i = 3 and then i += 2;

No problem :)/>/>

This post has been edited by pbl: 02 May 2013 - 06:48 PM

Was This Post Helpful? 0
  • +
  • -

#3 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10468
  • View blog
  • Posts: 38,799
  • Joined: 27-December 08

Re: PE#7 finding the 10,001 prime number

Posted 02 May 2013 - 06:43 PM

You can optimize some. Store the primes you already have. If the number isn't divisible by any of those, then it's a prime. So start at 2. Then the next number is 3, which is prime. Same for 5 and 7. Then when you get to 9, it's divisible by a prime in your list, so it's not prime.
Was This Post Helpful? 1
  • +
  • -

#4 CSatVTftw  Icon User is offline

  • New D.I.C Head

Reputation: 4
  • View blog
  • Posts: 42
  • Joined: 16-April 13

Re: PE#7 finding the 10,001 prime number

Posted 02 May 2013 - 07:00 PM

I know it's really inefficient. I haven't worked in Java in a long time so I'm just trying to get back into the basics again before I take my Java classes this summer semester.

I'm not understanding why the program is not counting up to 10002 even though it is looping that many times. When I add a System.out.println(count);, it spits out 10002, so why is it not giving me the 10001th prime?

Mac, can you explain that or give a short blip of an example?
Was This Post Helpful? 0
  • +
  • -

#5 Gungnir  Icon User is offline

  • Your Imaginary Friend

Reputation: 152
  • View blog
  • Posts: 527
  • Joined: 21-May 11

Re: PE#7 finding the 10,001 prime number

Posted 03 May 2013 - 04:43 AM

[spoiler alert!] You don't need to use long integers. I modified your code and got the answer 104,725 (which is correct).

You can half your execution time if you take into account that 2 is the only even prime number (so don't even bother checking them):
		  if(isPrime(num))
			  count++;		  
		  //After 2, skip every even number
		  if(num < 3)
			  num++;
		  else
			  num += 2;



I'm fairly certain that your method is incorrect. You should try something more like:
  public static boolean isPrime(int n) {
      for(int i = 3; i * i <= n; i += 2) {
          if(n % i == 0)
              return false;
      }
      return true;
  }



And whilst we're keeping count: On a 3GHz computer (variables, shmariables) with your current method:
10001th Prime = 104005
Execution time: 133 milliseconds


But if you fix it up a little (don't call Math.sqrt(), don't check even numbers):
10001th Prime = 104725
Execution time: 25 milliseconds


This post has been edited by Gungnir: 03 May 2013 - 04:56 AM

Was This Post Helpful? 0
  • +
  • -

#6 schutzzz  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 136
  • View blog
  • Posts: 338
  • Joined: 22-April 13

Re: PE#7 finding the 10,001 prime number

Posted 04 May 2013 - 02:45 PM

is your 10,001st even correct? on the website it's 104,743 and that's also what I got running mine.



public class Primes implements Runnable {
    
    public boolean isPrime(int checkNum) {
        double root = Math.sqrt(checkNum);
        for(int i = 2; i <= root; i++) {
            if(checkNum % i == 0)
                return false;
        }
        return true;
    }
    
    public void run() {
        int quantity = 10_001;
        int numberOfPrimes = 0;
        int entrant = 2;
        while(numberOfPrimes < quantity) {
            if(isPrime(entrant)) {
                System.out.println(": " + entrant);
                numberOfPrimes++;
            }
            entrant++;
        }
    }
    
    public static void main(String[] arguments) {
        (new Thread(new Primes())).start();
    }
    
}


Was This Post Helpful? 0
  • +
  • -

Page 1 of 1