Java代碼項目歐拉＃12

我的工作問題＃12項目歐拉，肚裏如下：通過將自然數時Java代碼項目歐拉＃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; 
    } 
}

來源

2013-08-16 earora4498

如果你打印出每次我並根據除數是多少更容易跟蹤 –

你確定它不是很慢，它仍然在運行？ – orangegoat

運行程序後，就好像它有一個非常長的運行時間，並看着你的算法，它確實（我以前做過這個問題）。您需要優化「除數」

擾流

如果更改的for（int i = 1;我< = N;我++）成（INT I = 1; I * I < = N;我++），它會大大減少執行時間。

更新：在沒有改變的情況下運行後，4分鐘內沒有答案，這違背了歐拉項目的一分鐘規則。更改後，在十秒內獲得答案。享受:)

來源

2013-08-16 21:11:56 ithenoob

這會減少執行時間，但它不會給你正確的答案。如果您使用上述修復程序，則需要考慮每個除數的其他「一半」。遞增計數器2.（counter + = 2;） –

@ Will.Beninger您只需要上升到數字的平方根，然後在最後乘以2。 –

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-02 05:00:35

這裏有2個備選方案：

1）遍歷所有的三角形，並停止如果currentSum（三角形數），有超過THRESHOLD除數
時間：1.79秒。

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）它基於coprime數字屬性。三角形數量等於n*(n+1)/2其中n和n+1是coprimes =>n和(n+1)/2被coprimes或n/2和n+1是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-14 18:34:13

使用「素因子分解」將使您的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 ^E1 p ^E2。P _ň^EN，其中n是一個整數，p _i：質數，

then，

＃積極的除數的：（E + 1）（E + 1）...（E _ñ + 1）

來源

2016-02-20 03:39:51

Java代碼項目歐拉＃12

回答

相關問題