수학 및 논리 퍼즐

소수

모든 자연수는 소수의 곱으로 나타낼 수 있다.

x = 2^j0 * 3^j1 * 5^j2 * 7^j3 * 11^j4 * 13^j5 * 17^j6 …

--

소수의 가분성(divisibility)

x = 2^j0 * 3^j1 * 5^j2 * 7^j3 * 11^j4 * 13^j5 * 17^j6 …

y = 2^k0 * 3^k1 * 5^k2 * 7^k3 * 11^k4 * 13^k5 * 17^k6 …

gcd = greatest common divisor = 최대공약수

gcd(x,y) = 2^min(j0,k0) * 3^min(j1,k1) * 5^min(j2,k2) ...

lcm = least common multiple = 최소공배수

lcm(x,y) = 2^max(j0,k0) * 3^max(j1,k1) * 5^max(j2,k2) ...

gcd(x,y)*lcm(x,y) = x*y

--

소수판별

에라토스테네스의 체 (max는 따로 define함)

void eratosthenes(bool *num)
{
    fill(&num[0],&num[max],1);
    for (int i = 4; i <= max; i += 2)
        num[i] = 0;
    for (int i = 3; i*i <= max; i += 2)
        if (num[i] == 1)
            for (int j = i*i; j <= max; j += 2 * i)
                num[j] = 0;
}

--

A∩B의 확률

P(A∩B) = P(B|A)P(A) = (P(B∩A)/P(A))*P(A)

--

A∪B의 확률

P(A∪B) = P(A)+P(B)-P(A∩B)