自然数除数的颜色

Question

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

他想用一种颜色给从 1 到 n 的所有自然数着色，这样他自己的一个数的所有约数都与该数具有相同的颜色。

该题要求找出最多可以使用多少种颜色。

例如，n = 5 你有：

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

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

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

问题出在质数上，所以我在想办法计算从1到n有多少个质数，然后把它加到需要的颜色数量上。

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

我是不是遗漏了什么，或者解决这个问题的唯一方法是找到 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");
}

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;
}

这returns一个布尔数组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

的所有数字的缓存

自然数除数的颜色

Colors of natural number divisors

c++

primes