Наибольший делитель числа, не равный ему самому

Question

Нужно написать функцию, которая возвращает самый большой делитель числа (которое не совпадает с самим введённым числом).

Примеры:

Число => делители => результат

10 => 1, 2, 5, 10 => 5
19 => 1, 19 => 1
35 => 1, 5, 7, 35 => 7
36 => 1, 2, 3, 4, 6, 9, 12, 18, 36 => 18
49 => 1, 7, 49 => 7

Answer 1

int solve(int n) {
  int i = 1;
  while ((long)i*i <= n) { // в диапазоне до корня от n
    i += 1;
    if (n % i == 0) // находим наименьший делитель
      return n / i; // делим на него, получаем наибольший
  }
  return 1;
}

Предложенная оптимизация:

@avp: Для четных решение очевидно, а значит можно проверять, начиная с 3 с шагом 2

int solve(int n) {
  if ((n & 1) == 0) return n >> 1;
  int i = 3;
  while ((long)i*i <= n) {
    if (n % i == 0)
      return n / i;
    i += 2;
  }
  return 1;
}

Код для вызова:

#include <stdio.h>
int main()
{
    int n;
    scanf("%d", &n);
    printf("%d\n", solve(n));
}

fiddle

Код без проблем переполнения:

#include <inttypes.h>
#define IMAX 4294967296ULL // (1ULL<<32) == sqrt(UINT64_MAX)

uint64_t solve(uint64_t n) {
  if ((n & 1) == 0) return n >> 1;
  uint64_t i = 3;

  while (i < IMAX && i*i <= n) {
    if (n % i == 0)
      return n / i;
    i += 2;
  }
  return 1;
}


#include <stdio.h>
#include <limits.h>
int main()
{
    printf("%" PRIu64 "\n", solve(118051));                  // 1
    printf("%" PRIu64 "\n", solve(118051ULL*11));            // 118051
    printf("%" PRIu64 "\n", solve(118051ULL*118051));        // 118051
    printf("%" PRIu64 "\n", solve(-1ULL));                   // 6148914691236517205
    printf("%" PRIu64 "\n", solve(18446744065119617025ULL)); // 6148914688373205675 // (IMAX - 1)**2
    printf("%" PRIu64 "\n", solve(18446744030759878681ULL)); // 4294967291 // max64(prime**2)
    printf("%" PRIu64 "\n", solve(18446744073709551557ULL)); // max64(prime), 14sec
}

БЛОГ НА HUSL

Наибольший делитель числа, не равный ему самому

Ответы (1 шт):