1

可能重复：
Project Euler 问题 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;
    }
}
4

2 回答 2

1

由于第 i 个三角形数有多少个除数并没有真正的规则或模式，因此您必须从头开始并测试每个数字。

所以优化（在我看来）只能在“有多少除数有这个数字”的问题上进行。

您只能检查所有素数（在检查期间建立素数集）。这将显着减少时间，尽管我不知道这是否已经是最快的解决方案（我对此表示怀疑）。

于 2012-07-03T08:33:41.480 回答
1

您需要优化找出给定数字的除数数量的方式。首先，对于每个d <= sqrt(n)这样的n%d==0，都有m=n/d这样的n%m==0和m >= sqrt(n)。这意味着您可以同时数两个数，停在sqrt(n).

但真正的优化是计算一个数的素因数分解，并从中找出除数的数量。

于 2012-07-04T05:37:12.990 回答