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

Question

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

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

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

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

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

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

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

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

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

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

Моя реализация Eratosthenes в следующем примере из Википедии:

/* 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");
}

Answer 1

Проблема в том, что вы используете алгоритм для одного числа снова и снова. Если вы хотите проверить много цифр, большая часть работы может быть использована повторно.

Я бы сделал что-то вроде этого:

bool * calculatePrimeArray(int n) 
{
    bool * ret = malloc(n*sizeof(*ret)+1);
    for(int i=0; i<n*sizeof(*ret)+1; i++) ret[i]=true;
    ret[0]=ret[1]=false;
    int cur = 2;
    while(cur < n/2+1) {
        if(ret[cur])
            for(int i=cur*2; i<n; i+=cur) ret[i] = 0;
        cur++;
    }
    return ret;
}

Возвращает логический массив ret, где ret [i] указывает, является ли i простым или нет.

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

Answer 2

Используя ответ @Bromax, я заработал 100 баллов во всех тестах на сайте:

#include <cstdlib>
#include <iostream>
#include <cmath>

#define PRIME 0
#define NOT_PRIME 1

bool *primes(int n) {
  bool *ret = (bool *)calloc(n + 1, sizeof(bool));
  ret[0] = ret[1] = NOT_PRIME;
  uint cur = 2;
  while (cur <= sqrt(n)) {
    if (ret[cur] == PRIME) {
      for (uint i = cur * cur; i <= n; i += cur) {
        ret[i] = NOT_PRIME;
      }
    }
    cur++;
  }
  return ret;
}

int main() {
  FILE *input = NULL;
  FILE *output = NULL;

  input = fopen("primcolor.in", "r");

  uint n;

  fscanf(input, "%d", &n);

  if (n < 1 || n > 50000000) {
    fclose(input);
    return 1;
  }

  output = fopen("primcolor.out", "w");

  if (n <= 3) {
    fprintf(output, "%d\n", n);
    fclose(input);
    fclose(output);
    return 0;
  }

  uint colors = 2;

  bool *a = primes(n);

  for (uint i = (n / 2 + 1); i <= n; i++) {
    if (a[i] == PRIME) {
      colors++;
    }
  }

  fprintf(output, "%d\n", colors);

  fclose(input);
  fclose(output);

  return 0;
}

Как и предполагалось, самый быстрый подход - создать массив, который будет использоваться в качестве кэша для всех чисел от 0 до n