소수

• 1과 자기 자신 이외의 약수를 가지지 않는 1보다 큰 자연수
• 즉, 소수는 두 개의 약수만 가지는 수이다.
  • 예를 들어, 2, 3, 5, 7, 11, 13 …
• 소수는 1과 자기 자신 외에는 어떤 수로도 나누어지지 않는다.

factor()

• 주어진 숫자의 소인수분해를 수행하는 함수이다.
• 입력 값에 따라 다르게 동작한다.
  • 숫자 : 소수들을 배열 형태로 반환
  • symboloc 변수 : symbolic 표현식으로 반환

예시

숫자인 경우

factor(823429252)

ans =

           2           2          59         283       12329

symbolic인 경우

syms x
F = factor(x^6-1)

F =
 
[x - 1, x + 1, x^2 + x + 1, x^2 - x + 1]

isprime()

• 주어진 숫자가 소수인지 여부를 판별하는 함수이다.
• 입력 값에 따라 다르게 동작한다.
  • 숫자 : 0 (true) or 1 (false)
  • 배열 : 0 (true)과 1 (false) 로 이루어진 논리형 배열

예시

tf = isprime([2 3 0 6 10])

tf =

  1×5 logical 배열

   1   1   0   0   0

primes()

• n보다 작거나 같은 모든 소수가 들어 있는 행 벡터를 반환한다.

primes(25)

ans =

     2     3     5     7    11    13    17    19    23

gcd()

• 두 숫자 또는 배열의 숫자 쌍에 대해 최대공약수 (Greatest Common Divisor, GCD)를 계산하는 함수이다.
  • 최대공약수 : 두 개 이상의 정수에서 공통으로 나눌 수 있는 가장 큰 양의 정수

예제

gcd(30, 56)

ans =

     2

lcm()

• 두 숫자 또는 배열의 숫자 쌍에 대해 최소공배수 (Least Common Multiple, LCM)를 계산하는 함수이다.
  • 최소공배수 : 두 개 이상의 정수에서 공통된 배수 중 가장 작은 양의 정수

예제

lcm(30, 56)

ans =

   840

유클리드 호제법

• 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나이다.
  • 정식 : 변수와 상수를 포함한 다항식
  • 호제법 : 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘

MATLAB 예제

function h = gcdiv(a, b)
	% 음수의 경우 절대값 처리
	if a < 0
		a = -a;
	end
	if b < 0
		b = -b;
	end
	
	while b > 0
		r = rem(a, b);
		a = b; b = r;
	end
	h = a;
end

호출

gcdiv(78696, 19332)

ans =

    36

1 ≤ i, j ≤ 100인 자연수 i와 j에 대하여 gcd(i, j) = 4를 만족하는 모든 i, j 순서쌍을 찾기

• 단, i ≤ j로 조합을 구성

cnt = 0;
for i = 1:100
    for j = i:100
        if gcd(i, j) == 4
            cnt = cnt + 1;
        end
    end
end
cnt

cnt =

   200