獲得第一個三角形數超過400個除數

Question

可能重複：
Project Euler Problem 12 - C++

我試圖讓超過400個除數（三角號如第一個三角形數： 1,3,6,10）。例如，三角形編號6有四個除數1,2,3,6。以下是我試圖用400個因子得到三角形數字

import java.math.BigInteger; 

public class IQ3 
{ 

     static int num1 = 1;  
     static int devideResult = 0;  

    public static void main(String[]args) 
    { 


     while(true) 
     { 
      int triangle = num1*(num1+1)/2; 

      if(devide(triangle)) 
      { 
       break; 
      } 

      num1++; 
     } 

    } 

    static boolean devide(int num) 
    { 
     boolean result = false; 
     int devideCounter = 2;  


     for(int i=1;i<=num/2;i++) 
      { 
       if(num%i == 0) 
       { 
        devideCounter++; 
        System.out.println("Devide Counter: "+devideCounter); 
        //System.out.println("i number: "+i); 
        //System.out.println("input number: "+num); 

        if(devideCounter>400) 
        { 
         System.out.println("Number: "+num); 
         result = true; 
         break; 
        } 
       } 
      } 

     return result; 
    } 
} 

但是這需要很長的時間，有時會崩潰。

但是，由於答案可能非常大，我想使用BigInteger。

import java.math.BigInteger; 

public class IQ2P2 
{ 

     static BigInteger num1 = new BigInteger("1"); 
     static BigInteger two = new BigInteger("2"); 
     static BigInteger one = new BigInteger("1"); 
     static BigInteger i = new BigInteger("1"); 
     static BigInteger zero = new BigInteger("0"); 


     static int devideResult = 0;   
    // static int devideCounter = 0; 

    public static void main(String[]args) 
    { 


     while(true) 
     { 
      BigInteger triangle = num1.multiply(num1.add(one)).divide(two); 

      if(devide(triangle)) 
      { 
       break; 
      } 

      num1.add(one); 
     } 

    } 

    static boolean devide(BigInteger num) 
    { 
     boolean result = false; 
     int devideCounter = 2;  


     while((i.compareTo(num))<(num.divide(two).intValue())) 
      { 
       if(num.remainder(i) == zero) 
       { 
        devideCounter++; 
        System.out.println("Devide Counter: "+devideCounter); 
        //System.out.println("i number: "+i); 
        //System.out.println("input number: "+num); 

        if(devideCounter>400) 
        { 
         System.out.println("Number: "+num); 
         result = true; 
         break; 
        } 
       } 
       i.add(one); 
      } 

     return result; 
    } 
} 

但是biginteger從來沒有返回任何東西。

請幫助我得到第一個有400多個因子的三角形數字。

注意：這不是一項功課。我不是學生。

以下是回答的響應

import java.math.BigInteger; 

public class IQ2 
{ 

     static long num1 = 1; 
     static long numberToAdd = 0; 
     static long devideResult = 0; 


     static long triangleNum = 1; 
    static long incrementer = 2; 
    // static int devideCounter = 0; 

    public static void main(String[]args) 
    { 


     while(true) 
     { 
      triangleNum += incrementer++; 

      if(devide(triangleNum)) 
      { 
       break; 
      } 

      num1++; 
     } 

    } 

    static boolean devide(long num) 
    { 
     boolean result = false; 
     int devideCounter = 2;  


     for(long i=1;i<=num/2;i++) 
      { 
       if(num%i == 0) 
       { 
        devideCounter++; 
        System.out.println("Devide Counter: "+devideCounter); 
        //System.out.println("i number: "+i); 
        //System.out.println("input number: "+num); 

        if(devideCounter>400) 
        { 
         System.out.println("Number: "+num); 
         result = true; 
         break; 
        } 
       } 
      } 

     return result; 
    } 
} 

Answer 1

您需要優化您找出給定數字的除數的方式。首先，對於每d <= sqrt(n)這樣的n%d==0，有m=n/d這樣的n%m==0和m >= sqrt(n)。這意味着你可以同時計數兩個，停在sqrt(n)。

但是真正的優化是計算一個數字的prime factorization，而不是從那裏找出amount of divisors。

Answer 2

至於有沒有真正的規則或模式第i個三角形的數量有多少除數了，你必須在一開始啓動並測試每個數字。

所以優化（在我看來）只能在「有多少除數有這個數字」 - 問題上進行。

您只能檢查所有素數（在檢查過程中建立素數集）。這會大大減少時間，但我不知道這是否是最快的解決方案（我懷疑它）。