自然数除数的颜色

Question

我有这个学校的问题关于一个人名Dorel，他的生日收到一个数字n。

他想用一种颜色从1到n的所有自然数字着色，这样他所有的数字除数都与数字相同。

该问题要求找出可以使用的最大颜色数。

例如，使用n = 5，你有：

• 1红色
• 2绿色
• 3蓝色
• 4绿色
• 5黄色

所以在这个例子中，我们需要4种颜色。

这个练习可以在here找到，但它是罗马尼亚语。

问题出现在素数上，所以我想到了一种方法来计算从1到n有多少素数，然后将其加到所需的颜色数量上。

我尝试过复杂的解决方案，如实施Miller-Rabin素性测试和Eratosthenes但是对于网站上的自动化测试，它仍然太慢了。

我错过了什么或解决这个问题的唯一方法是找到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的所有数字的缓存