2. 정수의 약수와 배수

① 약수와 배수의 정의

세 정수 a, b, q 사이에

a = b * q (단, b != 0)

인 관계가 있을 때, a 를 b 의 배수, b 를 a 의 약수 또는 인수라고 한다

function getDivisor(n:uint):Array
{

var array:Array = [];

   

var i:uint = 1;

while(i <= n)

{

if(n % i == 0)    array.push(i);

i++;

}

   

return array;

}

trace(getDivisor(344))

//////////////////

1,2,4,8,43,86,172,344

② 소수, 합성수

소수 : 1보다 큰 자연수 중에서 1과 그 자신의 수 이외에는 양의 약수를 가지지 않는 수
합성수 : 소수가 아닌 수

function isPrimeNumber(n:uint):Boolean
{

return n > 1 && getDivisor(n).length == 2;

}

trace(isPrimeNumber(7))
trace(isPrimeNumber(4))

//////////////////

true
false

③ 소인수분해

이건 좀 복잡할 수 있겠다... 그래서 주석을 달긴 했는데... 주석을 보면서 이해하자

정수를 소수들만의 곱으로 나타낸 수

function factorizationInPrimeFactors(n:uint):Array
{

// 인수를 구한다

var divisor:Array = getDivisor(n);

var cnt:uint = divisor.length;
// 1 과 자기 자신은 뺀다

divisor.splice(cnt - 1, 1);

divisor.splice(0, 1);

cnt -= 2;

// 인수 중에 소수들로만 재구성

var i:uint;

while(i < cnt)

{

var _n:Number = divisor[i];

if(!isPrimeNumber(_n))

{

divisor.splice(i, 1);

cnt --;

}

else    i++;

}

   

// 소수들의 곱으로 재구성

var _divisor:Array = [];

i = 0;

while(i < cnt)

{

_n = divisor[i];

var j:uint = 1;

while(n % Math.pow(_n, j) == 0)

{

_divisor.push(_n);

j++;

}

i++;

}

   

return    _divisor;

}

trace(factorizationInPrimeFactors(72))


///////////////////////////

2,2,2,3,3