程序员数学

来自 http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=math_for_topcoders

质数
优化后的朴素算法

public boolean isPrime (int n)
{
   if (n<=1) return false;
   if (n==2) return true;
   if (n%2==0) return false;
   int m=Math.sqrt(n);

   for (int i=3; i<=m; i+=2)
      if (n%i==0)
         return false;

   return true;
}

埃拉托斯特尼筛法（Sieve of Eratosthenes）

public boolean[] sieve(int n)
{
   boolean[] prime=new boolean[n+1];
   Arrays.fill(prime,true);
   prime[0]=false;
   prime[1]=false;
   int m=Math.sqrt(n);

   for (int i=2; i<=m; i++)
      if (prime[i])
         for (int k=i*i; k<=n; k+=i)
            prime[k]=false;

   return prime;
} 

GCD 最大公约数
辗转相除法

//assume that a and b cannot both be 0
public int GCD(int a, int b)
{
   if (b==0) return a;
   return GCD(b,a%b);
}

几何
矩形的笛卡尔表示法，(左下角，右上角)的坐标。
两个矩形R1:((x1,y1),(x2,y2));R2:((x3,y3),(x4,y4))
那么相交产生的矩形:((max(x1,x3),max(y1,y3)),(min(x2,x4),min(y2,y4)))
所以如果max(x1,x3)>min(x2,x4)或者max(y1, y3) > min(y2, y4)则不相交。
可以拓展到多维

Pick 定理，1899年
设P为平面上以格子点为顶点之单纯多边形，则其面积为
Area = B/2 + I - 1

其中 b 为边界上的格子点数，i 为內部的格子点数。(8)式叫做 Pick 公式。（http://baike.baidu.com/view/3207200.htm）

欧拉公式
简单多面体的顶点数V、面数F及棱数E间有关系
V+F-E=2 （可以用正四面体-每个面三角形来记 4+4-6=2）  （http://baike.baidu.com/view/398.htm）

进制（略）

分数和复数
分数可以用二维组来表示，做加法时要注意先求分母的最大公倍数

public int[] addFractions(int[] a, int[] b)
{
   int denom=LCM(a[1],b[1]);
   int[] c={denom/a[1]*a[0] + denom/b[1]*b[0], denom};
   return c;
}