-3

I have this school problem about a person name Dorel which for his birthday receives a number n.

He thought to color all natural numbers from 1 to n with one color so that all of his own divisors of a number have the same color as the number.

The problem asks to find out what is the maximum number of colors that can be used.

As an example, with n = 5 you have:

  • 1 red
  • 2 green
  • 3 blue
  • 4 green
  • 5 yellow

So in this example, we need 4 colors.

The exercise can be found here but it's in romanian.

The problem arise with prime numbers, so I was thinking of a way to calculate how many prime numbers there are from 1 to n and then add that to the amount of colors needed.

I tried complicated solutions like implementing Miller-Rabin primality test, and Eratosthenes but for the automated tests on the website it's still too slow.

Am I missing something or the only way to solve this problem is to find every prime between 1 and n?

My implementation of Eratosthenes following Wikipedia example:

/* 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");
}
genesisxyz
  • 778
  • 3
  • 14
  • 29
  • It's a bit unclear. What is the actual problem? Does your code work? If yes, is it fast enough? – klutt Apr 07 '19 at 20:54
  • I'm not sure what the question is here... – Borgleader Apr 07 '19 at 20:54
  • For one, you probably don't want `ceil(sqrt(n))` directly as the for loop continue condition. It's possible the stdlib you use doesn't mark them as pure, which would result in O(n) invocations computing the upper bound. – Cruz Jean Apr 07 '19 at 20:55
  • @Broman it works, it compiles and run, I think is not correct because some tests fail (on the website you can upload the code and test it, it gives lots of failures and most of them fail cause it's too slow) – genesisxyz Apr 07 '19 at 20:56
  • @Borgleader I'm trying to do the exercise, I think to solve this I need to find a way to count how many prime numbers there are between 1 and n, the problem is that every approach I have tried is too slow – genesisxyz Apr 07 '19 at 20:58
  • 2
    Have you searched for an algorithm? It's not like finding primes is a new problem. It is very easy to find fast code that does that. – klutt Apr 07 '19 at 21:05
  • 4
    Possible duplicate of [Which is the fastest algorithm to find prime numbers?](https://stackoverflow.com/questions/453793/which-is-the-fastest-algorithm-to-find-prime-numbers) – klutt Apr 07 '19 at 21:05
  • Although *counting* the number of primes < n is a distinct problem from *enumerating* the primes < n, I believe the fastest algorithm to count them is to first enumerate them. – President James K. Polk Apr 07 '19 at 22:49
  • @Broman I did search and I implemented also the Milller Rabin primality test but was still too slow for the tests, I will try the libraries on that link but I don't think its the solution, this is a 9 grade exercise, I think the solution is way easier – genesisxyz Apr 07 '19 at 23:28
  • 1
    Maybe this: https://en.m.wikipedia.org/wiki/Sieve_of_Eratosthenes – drescherjm Apr 08 '19 at 02:51

2 Answers2

1

The problem is that you use an algorithm for a single number over and over again. If you want to check a lot of numbers, a lot of the work can be reused.

I would do something like this:

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

This returns a Boolean array, ret, where ret[i] indicates if i is a prime or not.

If you want to make it more cache friendly, you can use bitfields instead of Boolean variables.

klutt
  • 30,332
  • 17
  • 55
  • 95
0

Using @Bromax answer I made it work and it scores 100 on all tests on the website:

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

As suggested, the fastest approach is to make an array that is used as cache for all numbers from 0 to n

genesisxyz
  • 778
  • 3
  • 14
  • 29