[소수]

에라토스테네스 체

var answer = [];
var N = 1000000;

var A = [];
for (var i=1; i<=N; i++) {
    A.push(i);
}
A[0] = 0;

for (var i=2; i<=Math.sqrt(N); i++) {
    if (A[i-1] != 0) {
        for (var j=i*2; j<=N; j+=i) {
            A[j-1] = 0;
        }
    }
}

for (var i=0; i<A.length; i++) {
    if (A[i] != 0) {
        answer.push(A[i]);
    }
}

GCD

function gcd(a,b) {
    var max = 0;
    var min = 0;
    if (a <= b) {
        max = b;
        min = a;
    } else {
        max = a;
        min = b;
    }

    /*var r = max % min;
    while (min % r != 0) {
        max = min;
        min = r;
        r = max % min;
    }
    return r;*/
    if (min == 0) return a;
    else return gcd(min, max % min);
}

최소공배수

function lcm(a,b) {
    return a*b/gcd(a,b);
}

소인수분해

var obj = {};
var result = N;
for (var i=2; i<=Math.sqrt(N); i++) {
    console.log(i,N)
    if (N % i == 0) {
        result -= result / i;
        while (N % i == 0) {
            N /= i;
            if (!obj[i]) obj[i] = 0;
            obj[i]++;
        }
        console.log(i,N)
    }
}

if (N > 1) result -= result / N;
if (!obj[N]) obj[N] = 0;
obj[N]++;
console.log(obj);

for문 돌고 난 뒤 N은 소수임.

(∵ 만약에 N이 합성수면 2~Math.sqrt(N) 사이의 정수를 인수로 가지고 있을꺼임.

근데 for문에서 다 제거했는데? ⇒⇐)