Наибольший делитель N (исключая себя)

Question

Я пытаюсь разделить список на подсписки, которые как можно больше. Если список не может быть разделен таким образом, я буду обрабатывать его по мере необходимости, но мне нужно получить наибольшее число, кроме самого N, которое равномерно разделяет N.

Я написал действительно наивное решение, но я чувствую, что должна быть какая-то формула или что-то делать это в постоянное время. Мой список не такой большой, максимальный размер - 1000. Это, вероятно, не критический путь, но есть ли лучший алгоритм?

public static int largestDivisor(int n){ 
    int divisor = 0; 
    for (int i = 1; i <= n/2; i++) 
     if (n % i == 0) 
      divisor = i; 

    return divisor; 
} 

Answer 1

Итерировать значения в обратном порядке. Просто верните первый, который вы найдете (он будет самым большим). Нечто подобное,

public static int largestDivisor(int n) { 
    for (int i = n/2; i >= 2; i--) { 
     if (n % i == 0) { 
      return i; 
     } 
    } 
    return 1; 
} 

В качестве альтернативы, вы можете сделать небольшое улучшение в @WillemVanOnsem «s answer и начать с нечетными значениями как;

public static int largestDivisor(int n) { 
    if (n % 2 == 0) { 
     return n/2; 
    } 
    final int sqrtn = (int) Math.sqrt(n); 
    for (int i = 3; i <= sqrtn; i += 2) { 
     if (n % i == 0) { 
      return n/i; 
     } 
    } 
    return 1; 
} 

Answer 2

Вы знаете, что если является делимым по б, также разделяемая на а/б и меньше б есть, тем больше а/б, так сразу вы нашли делитель, возвращение n/divisor:

public static int largestDivisor(int n){ 
    for(int i = 2; i <= n/2; i++) 
     if(n % i == 0) { 
      return n/divisor; 
     } 
    } 
    return 0; //or whatever you decide to return if there is no such divisor 
}

Это также быстрее, потому что:

1. делители, как правило, становятся более редкими, чем больше они получают; и
2. вы уже можете отказаться от sqrt(n).

Таким образом, наиболее эффективный подход был бы:

public static int largestDivisor(int n){ 
    int sqrtn = (int) Math.sqrt(n); 
    for(int i = 2; i <= sqrtn; i++) 
     if(n % i == 0) { 
      return n/divisor; 
     } 
    } 
    return 0; 
}

Answer 3

Я не знаю, если вы можете сделать это в постоянная время, но вы, конечно, можете сделать это за меньшее время, чем это.

Начните с 2 и пропустите все числа, проверяя, является ли n делением на это число. Когда вы переходите к числу, которое делит n, вы можете остановиться - ваш ответ n/i. Если вы дойдете до конца и все равно не разделите, то n будет простым, а ответ будет равен 1.

Вместо того, чтобы заканчиваться на n/2, если вы не найдете делителя, вы можете закончить с помощью √ n с этим методом, который уменьшит большой O.

Кроме того, вы можете начать с проверки, если он делится на 2, затем перейдите к 3 и проверьте только нечетные числа оттуда. (Если он был делимым на четное число, то он был делимым на 2.) Это не изменит большой O, но он должен сократить время обработки почти в два раза, так как вы проверяете только половину делителей.