Results 1 to 5 of 5
Like Tree1Likes
  • 1 Post By jim829

Thread: Efficient way to find Primes and sums of primes

  1. #1
    AlexGraal is offline Señor Member
    Join Date
    Jan 2014
    Posts
    184
    Rep Power
    0

    Default Efficient way to find Primes and sums of primes

    Java Code:
    class Program {
      public static void main (String[] args) {
        long max = 200; //add up all primes up to 200
        long ans = 0;
        for(long x = 2; x < max; x++) {
          if(isPrime(x)) {
            ans += x;
          }
        }
        System.out.println("Answer is: " + ans);
      }
      public static boolean isPrime(long x) {
        for(long z = 2; z < x; z++) {
          if(x % z == 0){
            return false;
          }
        }
        return true;
      }
    }
    This code adds up all of the primes before a certain number (max). Unfortunately, it is much too slow when you get up to bigger numbers - how can I do this more efficiently.

    BEFORE YOU ANSWER: Don't point me to the sieve of Eratosthenes, if that's what you are about to post - I'm not quite sure how to implement that kind of method into my program, so if you know, please explain and give me an example. Thanks

  2. #2
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    3,618
    Rep Power
    5

    Default Re: Efficient way to find Primes and sums of primes

    You don't need to the sieve to find the primes. But what you can do is store each prime you find and then only divide by those up to the square root of the target. It is still a trial by division method so it is sub-optimal to an actual sieve. More information is here --> Trial division - Wikipedia, the free encyclopedia. And don't forget to check out the reference articles.

    Regards,
    Jim
    AlexGraal likes this.
    The Java™ Tutorial | SSCCE | Java Naming Conventions
    Poor planning our your part does not constitute an emergency on my part.

  3. #3
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,533
    Blog Entries
    7
    Rep Power
    20

    Default Re: Efficient way to find Primes and sums of primes

    Quote Originally Posted by AlexGraal View Post
    BEFORE YOU ANSWER: Don't point me to the sieve of Eratosthenes, if that's what you are about to post - I'm not quite sure how to implement that kind of method into my program, so if you know, please explain and give me an example. Thanks
    Oh cool, you want advice but you don't want good advice because you already seem to know that you can't implement it ...

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  4. #4
    AlexGraal is offline Señor Member
    Join Date
    Jan 2014
    Posts
    184
    Rep Power
    0

    Default Re: Efficient way to find Primes and sums of primes

    Hmmmm, if only looking at the first half of the sentance, I guess that's what you'd get out of it. But the second half states what I was trying to say - aka, don't just tell me that it exists, because I already know about it. I'd much rather see how to implement it as I tried to and couldn't.

    Well, I guess since you answered and know about it, you can confirm or deny the way I was thinking about it.

    I was going to make an arraylist with all of the possible integers from 2 to 2000000, then I would start with the first integer, loopthrough the arraylist and remove anything that is evenly divisible by 2. Then move on to 3 and continue. Is that correct?


    And thanks Jim for the helpful reply :)

  5. #5
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,533
    Blog Entries
    7
    Rep Power
    20

    Default Re: Efficient way to find Primes and sums of primes

    Have a look at the BitSet class; it is way more efficient than an ArrayList for this purpose.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. Replies: 8
    Last Post: 08-27-2013, 08:50 PM
  2. Sum of primes have some trouble!
    By banglc11 in forum Threads and Synchronization
    Replies: 9
    Last Post: 04-27-2012, 10:05 PM
  3. 2d Array Sums Help
    By XxVashxX in forum New To Java
    Replies: 3
    Last Post: 10-17-2011, 06:20 PM
  4. Harmonic sums - Recursive
    By überfuzz in forum New To Java
    Replies: 4
    Last Post: 03-25-2011, 10:42 AM
  5. Problem with Sums and Averages in Sales Report
    By DavidEvans in forum New To Java
    Replies: 9
    Last Post: 04-21-2010, 08:57 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •