0

我正在为 Project Euler 解决问题 #12，如下所示：

三角形数的序列是通过添加自然数生成的。所以第 7 个三角形数是 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28。前十项是：

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

让我们列出前七个三角形数的因数：

1:1

3：1,3

6：1,2,3,6

10：1,2,5,10

15：1,3,5,15

21: 1,3,7,21

28：1、2、4、7、14、28

我们可以看到 28 是第一个有五个以上除数的三角形数。

第一个有超过 500 个除数的三角形数的值是多少？

这是我到目前为止的代码，但控制台在运行时不返回任何内容：

public class Euler12 {
    public static void main (String[] args) {
        int i = 1;
        int x = 2;
        boolean found = false;
        while (!found) {
            if (divisors(i) > 500) {
                System.out.println(i);
                found = true;
            }
            else {
                i +=x;
                x++;
            }
        }
    }

    public static int divisors (int n) {
        int counter = 0;
        for (int i = 1; i <= n; i++) {
            if (n % i == 0) counter++;
        }
        return counter;
    }
}
4

4 回答 4

2

运行程序后，似乎它的运行时间非常长，看看你的算法，确实如此（我以前做过这个问题）。您需要优化“除数”

剧透

如果将 for (int i = 1; i <= n; i++) 更改为 for (int i = 1; i*i <= n; i++)，它将大大减少执行时间。

更新：在没有更改的情况下运行后，4 分钟内没有答案，这违反了 Project Euler 的一分钟规则。更改后，十秒内得到答复。享受 ：）

于 2013-08-16T21:11:56.223 回答
1 
public class EulerProb12 {

    public static void main(String[] args) {

        int fib=0, count =1, i=1, incr=0;

        while (incr<5){         
            fib=0;
            while (i<=count){       
                fib = fib+i;
                i++;
            }

             i=1;
            incr=0;
            count++;

            for(int j=1; j<= Math.sqrt(fib); j++ ) // I used fib/2 here n result came late.
            {
                if(fib%j==0)
                {
                    incr++;
                }
            }
            incr*=2; // New logic when implemented along with sqrt
//          if(incr>150)
            System.out.println("Number: " + fib + " | Total Divisors: " + incr);        }
        System.out.println("Number: " + fib + " | Total Divisors: " + incr);
    }

}
于 2013-10-02T05:00:35.827 回答
1

这里有 2 个备选方案：

1）遍历所有三角形并在currentSum（三角形数）有超过THRESHOLD除数 时停止
Time: 1.79 seconds。

public class P12 {

    final static int THRESHOLD = 500;

    public static void main(String[] args) {
        System.out.println(getTriangle());
    }

    public static long getTriangle() {
        int n = 1;
        long currentSum = 0;
        while (!hasOverXDivisors(currentSum, THRESHOLD)) {
            currentSum += n;
            n++;
        }
        return currentSum;
    }

    private static boolean hasOverXDivisors(long nr, int threshold) {
        if ( nr <= threshold ) {
            return false;
        }
        int divisors = 0;
        int i;
        int sqrt = (int) Math.sqrt(nr);
        for ( i = 1 ; i <= sqrt ; i++ ) {
            if ( nr % i == 0 ) {
                divisors+=2;           // E.g.: (2, n/2), (3, n/3)
            }
        }
        if ( sqrt*sqrt == nr ){        // it was counted twice
            divisors--;
        }
        if ( divisors > threshold ) {
            return true;
        }
        return false;
    }

}

2) 它基于互质数属性。三角形数等于n*(n+1)/2where nand n+1are coprimes => nand (n+1)/2are coprimes or n/2and n+1are coprimes (这取决于n是偶数还是奇数)。
时间：61 毫秒。

public class P12 {

    final static int THRESHOLD_DIVISORS = 500;    

    public static void main(String[] args) {
        System.out.println(getTriangle(1));
    }

    public static long getTriangle(int n) {
        long numberOfDivisors = 0;
        long firstCoprime, secondCoprime;
        while (true) {
            if ( n % 2 == 0 ) {
                firstCoprime = getNumberOfDivisors(n/2);
                secondCoprime = getNumberOfDivisors(n+1);

            } else {
                firstCoprime = getNumberOfDivisors(n);
                secondCoprime = getNumberOfDivisors((n+1)/2);
            }           
            numberOfDivisors = firstCoprime * secondCoprime;
            if ( numberOfDivisors > THRESHOLD_DIVISORS ) {
                return n*(n+1)/2;
            }       
            n++;
        }
    }

    private static long getNumberOfDivisors(long nr) {
        int divisors = 0;
        int i;
        int sqrt = (int) Math.sqrt(nr);
        for ( i = 1 ; i <= sqrt ; i++ ) {
            if ( nr % i == 0 ) {
                divisors+=2;           // E.g.: (2, n/2), (3, n/3)
            }
        }
        if ( sqrt*sqrt == nr ){        // it was counted twice
            divisors--;
        }
        return divisors;
    }

}

我使用整数作为getTriangle()方法的参数，以便更容易改进此方法。您可以决定从大1于此特定情况的值开始。在这种情况下，您可以将时间减少至少 3 倍。

于 2014-11-14T18:34:13.123 回答
0

使用“素数分解”将使您divisor()更快更好。

尝试以下功能，getNumberOfDivisors()，而不是您的divisor().

public static long getNumberOfDivisors (long n) {
    int ret = 1;

    long factor = 2;
    while (factor <= n) {
        int temp = 1;
        while (n % factor == 0) {
            n /= factor;
            temp++;
        }
        ret *= temp;
        factor++;
    }

    return ret;
}

由于以下定理，该函数起作用：

如果 n = p 1 e1 p 2 e2 ... p n en，其中 n 是整数且 p i：素数，

然后，

# 正除数： (e 1 + 1) (e 2 + 1) ... (e n + 1)

于 2016-02-20T03:39:51.567 回答