Найти максимально возможное произведение элементов массива в заданном промежутке

Имеется число, которое мы раскладываем на простые множители. Нужно найти такое произведение его элементов, чтобы оно было максимально возможным для заданного промежутка, если для заданного промежутка невозможно найти такое произведение, то следует вывести -1.

using System.Collections.Generic;

namespace probka
{
 class Program
 {
     static List<int> Delitely(int k)//Нахождение всех делителей
     {
         var Delitely = new List<int>();
         var Del = 2;
         while (k % Del == 0)
         {
             Delitely.Add(Del);
             k /= Del;
         }
         Del = 3;
         while (Math.Pow(Del, 2) <= k)
         {
             if (k % Del == 0)
             {
                 Delitely.Add(Del);
                 k /= Del;
             }
             else
             {
                 Del += 2;
             }
         }
         if (k > 1)
         {
             Delitely.Add(k);
         }
         return Delitely;
     }
     static void Main(string[] args)
     {
         int a = int.Parse(Console.ReadLine());
         int[] mass = Delitely(a).ToArray();//массив простых множителей числа а
         int max = a;
         Console.WriteLine("Все делители: " + string.Join(" ", mass));
         int start = 1000;
         int end = 10000;
         int i = 0;
         if ((max >= start) && (max <= end))//если число уже входит в нужный промежуток
             max = max;
         else if (max < start)//если число меньше минимальной границы
             max = -1;
         else
             while (max > end)
             {
                 max /= mass[i];
                 i++;
                 if (i>=mass.Length)
                 {
                     max = -1;
                     break;
                 }
             }
         Console.WriteLine(max);
     }
 }
}

Если просто находить всевозможные произведения чисел, то программа получается неэффективная(при больших числах количество множителей много), поэтому я шел от самого числа и делил его на множители начиная сначала, но это идея провалилась, так как при введение числа а=1000000 программа выводит 3125, в то время , как 5×5×5×5×5×2=6250.