Самый большой простой множитель числа в Java

Кажется, у вас есть ошибка в вашем коде, например, когда вы вводите 16 largestPrime, функция возвращает 1. И это верно для случая, когда ввод представляет собой степень числа 3.

Подробное описание алгоритма: Вы можете сделать это, сохраняя три переменные: Число, которое вы пытаетесь разложить на множители (A) Текущее хранилище делителей (B) Наибольшее хранилище делителей (C) Первоначально пусть (A) будет числом, которое вас интересует. - в данном случае это 600851475143. Тогда пусть (B) равно 2. Имеем условие, проверяющее, делится ли (A) на (B). Если оно делится, разделите (A) на (B), сбросьте (B) на 2 и вернитесь к проверке, делится ли (A) на (B). В противном случае, если (A) не делится на (B), увеличьте (B) на +1, а затем проверьте, делится ли (A) на (B). Запускайте цикл до тех пор, пока (A) не станет равным 1. Возвращаемое вами (3) будет наибольшим простым делителем числа 600851475143.

 public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int t = in.nextInt();
    for(int a0 = 0; a0 < t; a0++){
        long n = in.nextLong();
        long A=n;
        long B=2;
        long C=0;
        while(Math.pow(B,2)<=A)
            {
            if(A%B==0)
                {
                C=B;
                A=A/B;
                B=2;
            }
            else
               B++;

        }
           if(A>=C)
            C=A;
           if(A==1)
               { C=2;
                break;
               }
         System.out.println(C);   
    }
}

Почему вы удаляете кратные 2 и кратные 3? Таким образом, если у вас есть число, представляющее собой любую комбинацию степеней 2 и 3, вы получите ответ как 1, что явно неверно.

Для этой задачи вы можете сделать наивный способ зацикливания от 2 до sqrt (n) и сохранить наибольшее число, которое делит n, когда вы закончите свой цикл, просто верните наибольший найденный делитель.

1 сбросьте петлю для 2 и 3. Если нет, вы не получите 2, 2x2, 3, 2x3, ... все кратные 2 и 3

2 измените свой цикл, чтобы остановиться на 2 (а не на 5):

while (n >= 2)
{

3 остановись, если 2

if (n==2) return 2;

4 петля из 2

а также

5 цикл до sqrt(n), с ‹= и не только ‹ (если нет, вы не получите Prime X Prime)

for (long i = 2; i <= Math.ceil(Math.sqrt(n)); i++)

Один из простых способов извлечения простых множителей выглядит следующим образом:

/**
 * Prime factors of the number - not the most efficient but it works.
 *
 * @param n - The number to factorise.
 * @param unique - Want only unique factors.
 * @return - List of all prime factors of n.
 */
public static List<Long> primeFactors(long n, boolean unique) {
  Collection<Long> factors;
  if (unique) {
    factors = new HashSet<>();
  } else {
    factors = new ArrayList<>();
  }
  for (long i = 2; i <= n / i; i++) {
    while (n % i == 0) {
      factors.add(i);
      n /= i;
    }
  }
  if (n > 1) {
    factors.add(n);
  }
  return new ArrayList<>(factors);
}

Эти первые петли - проблема. Они сократят все четные числа до 1, таким образом, 2 не будет использоваться в качестве множителя. Изменение кода для использования:

while (n > 2 && n % 2 == 0) {
  n = n / 2;  // remove all the multiples of 2
}
while (n > 3 && n % 3 == 0) {
  n = n / 3; // remove all the multiples of 2
}

У вас все еще есть проблемы - например. вы сообщаете, что наибольший простой делитель числа 25 равен 25, а наибольший простой делитель числа 49 равен 49.

Просто запустите этот код, используя свой и мой, чтобы увидеть, где ваш не работает:

for (long i = 1; i < 1000; i++) {
  long largestPrime = largestPrime(i);

  List<Long> primeFactors = primeFactors(i, true);
  if (primeFactors.size() > 0) {
    Collections.sort(primeFactors, Collections.reverseOrder());
    long highestFactor = primeFactors.get(0);
    if (largestPrime != highestFactor) {
      System.out.println("Wrong! " + i + " " + largestPrime + " != " + primeFactors);
    }
  } else {
    System.out.println("No factors for " + i);
  }
}