Need help? Check out our Support site, then


Secoud sourcecode is not working

  1. I have a post that uses the tag:

    [sourcecode language="css"]
    your code here
    [/sourcecode]

    As shown in: http://en.support.wordpress.com/code/posting-source-code/

    When I preview my entry, the first code works well, but the second one fails. I'm not even getting a box -- it's just the code text, unformatted.

    For reference, here's my entire post:

    Project Euler is an interesting website that offers about 400 different mathematics and computer programming questions. They range from easy (finding the sum of some set of big numbers) to impossible (navigating through Rudin-Shapiro sequences). Just recently, I solved the 179th question with the help of some Java code. While my program gave me the correct answer, the execution time on my Macbook Pro laptop was 80 seconds -- and there is an informal "60 seconds" rule that implies that code should be able to solve a problem in less than 60 seconds. So I wanted to determine in what ways I could optimize my code.

    Here was the question: Find the number of integers 1 < n < 10^7, for which n and n + 1 have the same number of positive divisors. For example, 14 has the positive divisors 1, 2, 7, 14 while 15 has 1, 3, 5, 15.

    This wasn't too bad for me. I already had a method that could compute the sum of the divisors of a number based on problem 23, so I revised it to add up the number of divisors, rather than the sum. Then I just iterated through each number from 1 to 10 million. Here was the first version of my code:

    [sourcecode language="java"]
    public class ProjectEuler179 {
    public static void main(String[] args) {
    long startTime = System.currentTimeMillis();
    int result = 0;
    int prevDivisors = 2;
    for (int i = 3; i <= 10000000; i++) {
    int currentDivisors = numberOfDivisors(i);
    if (currentDivisors == prevDivisors) {
    result++;
    }
    prevDivisors = currentDivisors;
    }
    System.out.println("The number of integers is: " + result + ".");
    long endTime = System.currentTimeMillis();
    System.out.println("Execution time: " + (endTime - startTime) + " ms.");
    }

    public static int numberOfDivisors(int x) {
    int numOfDivisors = 2;
    for (int k = 2; k <= Math.sqrt(x); k++) {
    if (x % k == 0) {
    if (k != Math.sqrt(x)) {
    numOfDivisors += 2;
    } else {
    numOfDivisors += 1;
    }
    }
    }
    return numOfDivisors;
    }
    }
    [/sourcecode]

    I'm not going to say what the answer was, but as mentioned before, the execution time (endTime - startTime) was about 80 seconds. Looking at the code, the limiting factor is the 10 million calls I make to the method numOfDivisors(). So how can I improve this? In other words, how can I avoid making all those calls to my static method here?

    To start, I initialized an array of 10,000,001 elements, called divs, where divs[x] refers to the number of divisors of x. Then, I took advantage of two nested for loops to make sure that each entry of divs[x] did hold the number of divisors of x. The outer for loop went from int i = 1 to 10,000,000, and the inner for loop went as far from int j = 1 to as large a number such that i*j <= x. This implies that all factors for a number are counted!

    The updated code is as follows:

    [sourcecode language="java"]
    public class ProjectEuler179 {
    public static void main(String[] args) {
    long startTime = System.currentTimeMillis();
    int result = 0;
    int[] divs = divisors(10000000);
    for (int i = 2; i < 10000000; i++) {
    if (divs[i] == divs[i+1]) {
    result++;
    }
    }
    System.out.println(result);
    long endTime = System.currentTimeMillis();
    System.out.println("Execution time: " + (endTime - startTime) + " ms.");
    }

    public static int[] divisors(int x) {
    int[] divs = new int[x + 1];
    for (int i = 1; i <= x; i++) {
    for (int j = 1; i * j <= x; j++) {
    divs[i*j]++;
    }
    }
    return divs;
    }
    }
    [/sourcecode]

    It gave me the right answer. And the runtime was an amazingly quick 1.9 seconds -- much, much better!

    The blog I need help with is seitad.wordpress.com.

  2. Never mind, it works. For some reason, WordPress kept changing the second sourcecode tag to say something weird, like

    ;quote java ;quote

    so I had to keep fixing it. It turned out all right.

  3. Well that's good news. Hopefully it will be smooth sailing for you from here on.

Topic Closed

This topic has been closed to new replies.

About this Topic