数字着色

时间：2009-08-08 来源：ubuntuer

给1~N的每一个数字标记一种颜色，使得其中任意两个数字A,B，如果A可以整除B，则A和B必须标记不同的颜色，要求所使用的颜色最少，并得到1~N的每一个数字所标记的颜色（用数字表示）。请编写程序解决这个问题。
例子：
输入：（1<= N <=10000）
16
输出：
5
1 2 2 3 2 3 2 4 3 3 2 4 2 3 3 5
这个关键是分析清楚对于一个非质数其颜色为A[i*j] = max(A[i],A[j])+1,质数就为A[1] + 1. note：我这里分析的时候是按数组下标为1分析的。程序内面是按0。其实这题如果是单单只求个数的话，就好弄了。就为sqrt(N*1.0)+1.刚又发现如果pow(2,m)<N<=pow(2,n)得话,就是n。仅仅是一家之言^_^ 好了,下面是代码。经过了一定得测试.大家跑跑要是有问题，再说。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAX(a,b) (a)>(b)?(a):(b)
int main(int argc, char *argv[])
{
  int N;
  int i;
  int j;
  int tmp;
  printf("Please input the number you want to count:\n");
  scanf("%d",&N);

  int sqrt_num = (int)sqrt(N*1.00);
  int binary_num = N/2;

  int A[N];
  A[0] = 1;
  for(i=1;i<=N;i++)
    A[i] = A[0]+1;

  for(i=2;i<=sqrt_num;i++)
   for(j=i;j<=binary_num;j++)
    {
      if(i*j > N)
        continue;

      tmp = MAX(A[i-1],A[j-1]) + 1;
      if(tmp > A[i*j-1])
        A[i*j-1] = tmp;

      printf("num:%d color:%d\n",i*j, A[i*j-1]);
    }

  for(i=0;i<N;i++)
    printf("%2d ",i+1);

  printf("\n");
  for(i=0;i<N;i++)
    printf("%2d ",A[i]);

  system("PAUSE");
  return 0;
}