Цвета натуральных делителей чисел

У меня есть школьная задачка о человеке по имени Дорел, который на день рождения получил число n.

Он решил покрасить все натуральные числа от 1 до n в один цвет так, чтобы все его собственные делители числа были одного цвета с этим числом.

Задача состоит в том, чтобы выяснить, какое максимальное количество цветов можно использовать.

Например, с n = 5 у вас есть:

• 1 красный
• 2 зеленый
• 3 синие
• 4 зеленый
• 5 желтый

Итак, в этом примере нам нужно 4 цвета.

Упражнение можно найти под номером здесь, но оно на румынском языке.

Проблема возникает с простыми числами, поэтому я подумал о том, как вычислить, сколько простых чисел существует от 1 до n, а затем добавить это к количеству необходимых цветов.

Я пробовал сложные решения, такие как реализация теста простоты Миллера-Рабина и Эратосфена, но для автоматических тестов на веб-сайте это все еще слишком медленно.

Я что-то упустил или единственный способ решить эту проблему — найти каждое простое число от 1 до n?

Моя реализация Эратосфена по примеру Википедии:

/* https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Overview */
void prime(uint n) {
  if (n < 1) return;

  /* Create a list of consecutive integers from 2 through n: (2, 3, 4, ..., n). */
  uint size = n - 1;
  uint *list = (uint *)malloc(sizeof(uint) * size);
  for (uint i = 0; i < size; i++) {
    list[i] = i + 2;
  }

  /* Initially, let p equal 2, the smallest prime number. */
  uint p = 2;

  uint c = 1;

  while (c < n) {
    /*
     * Enumerate the multiples of p by counting in increments of p from 2p to n,
     * and mark them in the list (these will be 2p, 3p, 4p, ...; the p itself should not be marked).
     */
    for (uint i = c; i < size; i++) {
      if (list[i] % p == 0) {
        list[i] = 0;
      }
    }

    /*
     * Find the first number greater than p in the list that is not marked.
     * If there was no such number, stop.
     * Otherwise, let p now equal this new number (which is the next prime).
     */
    while (c < n) {
      if (list[c] > p) {
        p = list[c++];
        break;
      }
      c++;
    }
  }

  /* the numbers remaining not marked in the list are all the primes below n */
  for (uint i = 0; i < size; i++) {
    if (list[i] != 0) {
      printf("%d ", list[i]);
    }
  }
  printf("\n\n");
}