java - 获取第一个除数超过 400 的三角形数

Question

Possible Duplicate:
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;
    }
}

但是大整数从未返回任何内容。

请帮我求第一个约数超过 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从那里。