Sunday, June 14, 2009

Puzzle 33 – Prime Number (Optimization Series puzzle -1)

Language – Java | Type – Concept | Last date 17-Jun-2009 9:00 p.m. IST | Points 3

Lately I have been pretty interested in project Euler. Project Euler is a series of challenging mathematical/computer programming problems that require the use of a computer and programming skills to solve problems.

If you haven't been there yet I suggest do have a look.

I sure people love the idea of writing optimized code – something I usually don’t quite agree with. I would trade cheeky (and hard to understand) optimized code for easy and maintainable code. But that’s just me!!

Project Euler has thumb rule – No problem should take more than a min to solve. Since the code I write can usually take a long time to run it would be great if you folks could help me out a bit!

package com.sam.twisters.euler;
/*
* The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
* Find the sum of all the primes below two million.
*/
public class Proj10 {

/* Method that returns true if n is prime otherwise returns false*/
/* Use the brute force method! */
/* I have optimized it so that it skips even numbers.*/
public static boolean isPrime(long n){
boolean isPrime = true && (n==2 || n%2!=0);
for(long i=3; i<n&&isPrime;i+=2){
if(n%i ==0){
isPrime
= false;
}
}
return isPrime;
}

public static void main(String[] args) {
long startTime = System.nanoTime();

long sum = 0;
int n=2;
do{
if(isPrime(n)){sum+=n;}
n
++;
}
while(n < 2000000);
System.out.println(sum);

long estimatedTime = System.nanoTime() - startTime;
System.out.println((
float)estimatedTime/1000000000);
}
}


You can view the code @ http://www.blogtrog.com/code.aspx?id=1ce259ec-11f6-42bc-b03a-6aa9bf100a90

I got a few rules though.
1. This code takes about 30 minutes to run. Get it to run in under 1 min.
2. You see while it's really great that you have decided to help me – I really don't want you to mess up my entire code. So here is the deal – you can change a maximum of 18 characters (yes that's all).
3. What constitutes a character change?
a. Inserting a character – each character (including space) that you add to the existing code.

b. Deleting a character – each character (including space) that you delete from the existing code.

c. Over writing a character – well you cannot do that. You could delete and insert but you cannot over write.

d. Cut Paste - Special Rule for cut paste is you can cut code from the existing code and paste it somewhere (except inside a comment) else in the code without using up single char.
To illustrate you could cut n%2==0|| from if(n%2==0||n%i ==0){ (line 12)
And paste it at if(n%2==0||isPrime(n)){sum+=n;} (line 27) without using up a single char. Just remember its cut-paste and not copy-paste.

If all the rules seem a bit complicated - well just remember the main rule - 18 characters - either addition or deletion counts!

Hint – I would look carefully at the prime number algorithm for possible optimizations! Its a mathematical questions - so the answer could be with Math.

Link of the day -- http://projecteuler.net

(P.S – Feel free to add as many comments as needed to explain your optimization!
If the rules are not 100% clear – don't worry they will be once you see the answer(s). Please do let me know what you think of this type of question – would you like to see more? This one is purposefully simple -;)

Also if you want to re-write the entire code ,feel free to do so and leave a comment – Just that I won’t count that solution towards the score - that's all, still would be great to hear from you!)

Got an answer? Do leave it here.

9 comments:

  1. Math.sqrt() :)

    public static boolean isPrime(long n) {
    boolean isPrime = true && (n == 2 || n % 2 != 0);
    for (long i = 3; i <= Math.sqrt(n) && isPrime; i += 2) {
    if (n % i == 0) {
    isPrime = false;
    }
    }
    return isPrime;
    }

    ReplyDelete
  2. Under 4 secs on my computer ( laptop with dual core 1.9GHz). Changed the for loop in isPrime() from

    for(long i=3; i < n&&isPrime;i+=2){
    to
    for(long i=3; i <=Math.sqrt(n)&&isPrime;i+=2)

    Everything after the sqrt is redundant.

    You also seem to have a lot of other redundant code and messy code in there. ie. instead of putting in &&isprime and return isPrime at the end, just return false when you realise it isnt a prime.

    Also skipping multiples of two will do very little given how fast they will get eliminated anyway.

    2%2 == 0 so n==2 || n%2 == 0 is redundant.

    The other thing you can do is store the primes in an ArrayList and only test against them. The code for that is here, and runs on my computer in just over a second.

    ReplyDelete
  3. This is probably the anticipated solution:
    change the for loop as follows:
    for(long i=3; i<Math.sqrt(n)+1&&isPrime;i+=2)

    this is only 13 characters added but the runtime is already well below 6 seconds without warmup.

    of course there is a lot of trivial things left that can be done to improve it even more: changing another 25 characters or so brings us down to about 1 second.

    Of course the best performance can be achieved using a (trivial) LUT like this:

    long sum = 142913828922L;
    int n=2;
    do{
    //if(isPrime(n)){sum+=n;}
    n++;
    }while(n > 2000000);

    That is less than 18 changes and takes far less than a millisecond.
    For fixed tasks like this, computing the result beforehand and hardcoding it is the best solution.

    ReplyDelete
  4. From about 20 minutes to about 2 seconds (on my computer) with only three changes:

    insert *i and a = in line 13:
    for(long i=3; i*i<=n&&isPrime;i+=2){

    ReplyDelete
  5. If a number n has factors then at least 1 factor <= root(n).
    root(2000000) is roughly 1415
    Do not try a mod beyond 1415.

    ReplyDelete
  6. yes answer for this is Math ==> Math.sqrt()

    ReplyDelete
  7. Line 13 should be:
    for(long i=3; i<=Math.sqrt(n)&&isPrime;i+=2){

    Performance: about 6.5 sec

    ReplyDelete
  8. My solution is:

    just change the method isPrime to:

    public static boolean isPrime(long n) {
    boolean isPrime = true && (n == 2 || n % 2 != 0);

    for (long i = 3; i <= Math.sqrt(n) && isPrime; i += 2) {
    if (n % i == 0) {
    isPrime = false;
    }

    }
    return isPrime;
    }


    A better solution would be (but too many char changes):

    public static boolean isPrime(long n) {
    boolean isPrime = true && (n == 2 || n % 2 != 0);
    long temp = (long) Math.sqrt(n);
    for (long i = 3; i <= temp && isPrime; i += 2) {
    if (n % i == 0) {
    isPrime = false;
    }

    }
    return isPrime;
    }

    ReplyDelete
  9. Runs in about 8.6 seconds.. gives the result: 142913828922


    package com.sam.twisters.euler;
    /*
    * The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
    * Find the sum of all the primes below two million.
    */
    public class Proj10 {

    /* Method that returns true if n is prime otherwise returns false*/
    /* Use the brute force method! */
    /* I have optimized it so that it skips even numbers.*/
    public static boolean isPrime(long n){
    boolean isPrime = true && (n==2 || n%2!=0);
    for(long i=3; i<Math.sqrt(n)+1&&isPrime;i+=2){
    if(n%i ==0){
    isPrime = false;
    }
    }
    return isPrime;
    }

    public static void main(String[] args) {
    long startTime = System.nanoTime();

    long sum = 0;
    int n=2;
    do{
    if(isPrime(n)){sum+=n;}
    n++;
    }while(n < 2000000);
    System.out.println(sum);

    long estimatedTime = System.nanoTime() - startTime;
    System.out.println((float)estimatedTime/1000000000);
    }
    }

    ReplyDelete

Solution for this question?