找到第一个具有50个因子的三角形数？

Question

找到第一个具有50个因子的三角形数？

5

-----需要修改的代码请求--------

问题：计算具有50个因子的快速三角形数？

详细说明：假设有一个系列

   1 : 1
   3 : 1+2
   6 : 1+2+3 
   10 : 1+2+3+4
   15 : 1+2+3+4+5
   21 : 1+2+3+4+5+6
   28 : 1+2+3+4+5+6+7

1、3、6、10、15、21和28是三角数序列中的数字。

让我们看看这个数字的因数。

    Number factors         Count
    1     : 1               1              
    3     : 1,3             2
    6     : 1,2,3,6         4
    10    : 1,2,5,10        4
    15    : 1,3,5,15        4
    21    : 1,3,7,21        4
    28    : 1,2,4,7,14,28   6

这里的6是第一个拥有4个因数的三角形数。即使10、15、21也有4个因数，但它们不是第一个。同样地，我们以2为例，它有1和2两个因数。对于数字3也是如此，它有1和3两个因数。

但根据问题，答案是3而不是2，因为2不在三角形数列列表中，即使它比3更快。

- Chandan Kumar

这个问题似乎不适合讨论，因为它涉及到数学而非编程。 - razlebe

3

Project Euler（欧拉计划）是一个面向数学和计算机科学爱好者的网站，提供一系列具有挑战性和趣味性的问题。该网站旨在帮助人们提高他们的数学和编程能力，并且鼓励他们探索新的思考方式。链接中的问题号12涉及三角形数，需要找到第一个具有500个或更多因子的三角形数。 - JNF

是的JNF，但我需要的是针对上述问题的适当解决方案(步骤/逻辑)。我得到了输出，但我希望能编写出更好的代码。这就是为什么请求一个比我的给定逻辑更好的解决方案。 - Chandan Kumar

2

据我所知，当你回答Project Euler的问题时，你会自动获得访问论坛主题的权限，以便与世界分享你的解决方案并阅读其他人的解决方案。这些帖子是更好逻辑的重要来源。 - akalenuk

@razlebe - 代码在 OP 自己的答案中。虽然不是一个好的方法，但至少有点东西。 - Corak

显示剩余4条评论

4个回答

3

解决方案：让我将问题分解成多个模块。

1）找到一个数的三角数序列。 2）将所有识别出的数字存储在整数列表中。 3）找到特定数字的因子数量。 4）循环遍历每个三角数序列项并找到每个数字的因子计数。 5）检查第一个计数为50的数字，然后显示该值。 6）编写break语句仅显示第50个数字。

程序

using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text;

namespace IsNumberTringularSeriesConsoleApp
{ 
    class Program
    {
        /// <summary>
        /// Listing all numbers comes under Triangular series.
        /// </summary>
        /// <param name="number"></param>
        /// <returns></returns>
        static List<int> GetTriangularNumbers(int number)
        {
            List<int> lstTriangularNumbers = new List<int>();
            int i;
            int sum = 0;
            int triangularNumber = 0;
            for (i = 1; i < number; i++)
            {
                sum = sum + i;
                triangularNumber = sum;
                lstTriangularNumbers.Add(triangularNumber);
            }
            return lstTriangularNumbers;
        }

        /// <summary>
        /// returns(count) the number of factors for each number
        /// </summary>
        /// <param name="number"></param>
        /// <returns></returns>
        public static int FactorCount(int number)
        {
            List<int> factors = new List<int>();
            int max = (int)Math.Sqrt(number);  //round down
            for (int factor = 1; factor <= max; ++factor)
            { 
                //test from 1 to the square root, or the int below it, inclusive.
                if (number % factor == 0)
                {
                    factors.Add(factor);
                    if (factor != number / factor)
                   {
                     // Don't add the square root twice!  
                        factors.Add(number / factor);
                   }
                }
            }
            return factors.Count;
        }

        static void Main(string[] args)
        {
            List<int> lstTriangularNumbers = new List<int>();
            List<int> factors = new List<int>();
            int count = 0;
            //Getting the list of numbers comes under triangular series till 5000
            lstTriangularNumbers = GetTriangularNumbers(5000);

            foreach (int number in lstTriangularNumbers)
            {
                /*
                 * Calling the FactorCount(number) function to check no of factors 
                 * available for the specific triangular number - number.
                 */
                 count = FactorCount(number);
                 //Console.WriteLine("No of factors for : " + number + " is : " + count);
                if (count == 50)
                {
                    Console.WriteLine("No of factors for first Triangular Number : " + number + " is : " + count);
                    break;
                }
            }
            Console.ReadLine();
        }
    }
}

- Chandan Kumar

@HighPerformanceMark：OP 可以使用 BigInteger 进行替换，尽管可能需要一些工作。 - Michael Bray

老板，它的输出是“第一个三角数因子的数量为：3357936是50”，这是正确的。我需要一个更好的代码。 - Chandan Kumar

首先要“改进”的是：你的FactorCount和GetFactors基本上具有相同的主体。所以只需将FactorCount设置为return GetFactors(number).Count;。再次查看mathblog，以了解其他大幅减少执行时间的方法。或者你所说的“更好”的代码是什么意思？ - Corak

我会把GetTriangularNumbers修改成这个样子:

public static IEnumerable<int> GetTriangularInt32() { var sum = 0; var i = 1; while (Int32.MaxValue - sum >= i) { sum += i++; yield return sum; } }

既然你已经用了foreach和break，那么你就不必事先创建不必要的数字。 - Corak

3

这是我的答案。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace TriangularSeries
{
    class MyClass
    {
        static void Main(string[] args)
        {
            int result;
            TriangularSeries aSeries = new TriangularSeries();
            result = aSeries.TSeries();
            Console.WriteLine("The first Triangular Series number that has 50Factors is : " + result);
            Console.Read();
        }
    }

    //Find the Triangular Series numbers
    class TriangularSeries
    {
        public int TSeries()
        {
            int fCount = 0, T1 = 1, i = 1, T2 = 0, fval = 0;
            while (fCount != 50)
            {
                i += 1;
                T2 = T1 + i;

                fCount = CalcFactors(T1);
                fval = T1;                   
                T1 = T2;

            }
            return fval;
        }

        public int CalcFactors(int num1)
        {

            List<int> factors = new List<int>();
            int max = (int)Math.Sqrt(num1);  //round down
            for (int factor = 1; factor <= max; ++factor)
            {
                //test from 1 to the square root, or the int below it, inclusive.
                if (num1 % factor == 0)
                {
                    factors.Add(factor);
                    if (factor != num1 / factor)
                    {
                        // Don't add the square root twice!  
                        factors.Add(num1 / factor);
                    }
                }
            }
            return factors.Count;

        }
    }   
}

- user3001117

感谢您的解决方案，shiny。 - Chandan Kumar

1

这是我的C语言程序

#include<stdio.h>
int i;
int num1=0,num2=1;
int a[3000];
int tri_series()         //This function finds the Triangular series numbers
{
    for(i=0;num2<=3000;i++)
    {
    num1=num1+num2;
    a[i]=num1;
    num2++;
    }
}
int main()
{
tri_series();            //Calling the function tri_series
int num,count;
    for(i=0;i<=3000;i++)
    {
      count=0;
      for(num=1;num<=a[i];num++)
      {
        if(a[i]%num==0)  //Finds the factors of each Triangular Series Number 
        count=count+1;   
      }
      if(count==50)      //Break at the first Triangular Series Number having 50 factors
      {
       printf("%d:%d\t",a[i],count);
       break;
      }
    }
}

性能问题：当执行此代码时，会出现性能问题。它需要“一分钟”才能执行并显示输出。

- Petryanu

谢谢你，Anu。感谢你提供 C 语言版本的答案。这对于 C 程序员来说将会很有帮助。 - Chandan Kumar

但是需要进行一些修改。num2未定义，main函数没有返回任何值。请修改程序以便对C程序员有所帮助。 - Chandan Kumar

1

a[i]的值在主函数中被打印出来，tri_series函数只是在主函数中被定义和调用。感谢您的纠正，Chandan。 - Petryanu

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Dmitry Bychenko · Accepted Answer

第2591个三角数为3357936，是第一个恰好有50个因子的三角数： 1、2、3、4、6、8、9、12、16、18、24、27、36、48、54、72、81、108、144、162、216、324、432、648、1296、2591、5182、7773、10364、15546、20728、23319、31092、41456、46638、62184、69957、93276、124368、139914、186552、209871、279828、373104、419742、559656、839484、1119312和1678968。

第12375个三角数为76576500，是第一个至少有500个因子的三角数（实际上有576个因子）： 1、2、3、4、5、6、7、9、10、11等等，到19144125、25525500、38288250、76576500结束。

第1569375个三角数为1231469730000，是第一个恰好有500个因子的三角数。

只要你能够得到除数，解决方案代码本身就很容易。

   public static long Solution(int factorsCount) {
      for (long i = 1; ; ++i) {
        long n = i * (i + 1) / 2;

        IList<long> factors = GetDivisors(n);

        // This code tests if a triangle number has exactly factorsCount factors
        // if you want to find out a triangle number which has at least factorsCount factors
        // change "==" comparison to ">=" one:
        // if (factors.Count >= factorsCount)  
        if (factors.Count == factorsCount) 
          return n;
      }
    }

  ...

  long solution = Solution(50);

如果您没有得到获取数字因子的例程，可以使用此例程：

// Get prime divisors 
private static IList<long> CoreGetPrimeDivisors(long value, IList<int> primes) {
  List<long> results = new List<long>();

  int v = 0;
  long threshould = (long) (Math.Sqrt(value) + 1);

  for (int i = 0; i < primes.Count; ++i) {
    v = primes[i];

    if (v > threshould)
      break;

    if ((value % v) != 0)
      continue;

    while ((value % v) == 0) {
      value = value / v;

      results.Add(v);
    }

    threshould = (long) (Math.Sqrt(value) + 1);
  }

  if (value > 1)
    results.Add(value);

  return results;
}

/// <summary>
/// Get prime divisors 
/// </summary>
public static IList<long> GetPrimeDivisors(long value, IList<int> primes) {
  if (!Object.ReferenceEquals(null, primes))
    return CoreGetPrimeDivisors(value, primes);

  List<long> results = new List<long>();

  while ((value % 2) == 0) {
    results.Add(2);

    value = value / 2;
  }

  while ((value % 3) == 0) {
    results.Add(3);

    value = value / 3;
  }

  while ((value % 5) == 0) {
    results.Add(5);

    value = value / 5;
  }

  while ((value % 7) == 0) {
    results.Add(7);

    value = value / 7;
  }

  int v = 0;
  long n = (long) (Math.Sqrt(value) / 6.0 + 1);
  long threshould = (long) (Math.Sqrt(value) + 1);

  for (int i = 2; i <= n; ++i) {
    v = 6 * i - 1;

    if ((value % v) == 0) {
      while ((value % v) == 0) {
        results.Add(v);

        value = value / v;
      }

      threshould = (long) (Math.Sqrt(value) + 1);
    }

    v = 6 * i + 1;

    if ((value % v) == 0) {
      while ((value % v) == 0) {
        results.Add(v);

        value = value / v;
      }

      threshould = (long) (Math.Sqrt(value) + 1);
    }

    if (v > threshould)
      break;
  }

  if (value > 1) {
    if (results.Count <= 0)
      results.Add(value);
    else if (value != results[results.Count - 1])
      results.Add(value);
  }

  return results;
}

/// <summary>
/// Get all divisors
/// </summary>
public static IList<long> GetDivisors(long value, IList<int> primes) {
  HashSet<long> hs = new HashSet<long>();

  IList<long> divisors = GetPrimeDivisors(value, primes);

  ulong n = (ulong) 1;
  n = n << divisors.Count;

  for (ulong i = 1; i < n; ++i) {
    ulong v = i;
    long p = 1;

    for (int j = 0; j < divisors.Count; ++j) {
      if ((v % 2) != 0)
        p *= divisors[j];

      v = v / 2;
    }

    hs.Add(p);
  }

  List<long> result = new List<long>();

  result.Add(1);

  var en = hs.GetEnumerator();

  while (en.MoveNext())
    result.Add(en.Current);

  result.Sort();

  return result;
}

/// <summary>
/// Get all divisors
/// </summary>
public static IList<long> GetDivisors(long value) {
  return GetDivisors(value, null);
}