1

重複の可能性:
Project Euler Problem 12 - C++

400 を超える除数を持つ最初の三角形の数を取得しようとしています (三角形の数など: 1,3,6,10)。たとえば、三角形番号 6 には 4 つの約数 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/dn%m==0m >= sqrt(n)sqrt(n)

しかし、実際の最適化は、代わりに数値の素因数分解を計算し、そこから約数を見つけることです。

于 2012-07-04T05:37:12.990 に答える