Треугольник с номером #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, 3357936
Номер треугольника #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);
}
person
Dmitry Bychenko
schedule
09.07.2013