[기초 알고리즘] 수학

1. 소수

소수란?

• 1과 자기 자신으로만 나누어지는 수 입니다.

 

판정법

for (int i = 2; i < N; i++) {
    if (N % i == 0) 
    	return false;
}

return true;

• 2부터 N-1까지 반복합니다.
• 반복하는 숫자가 N으로 나머지 연산하여 0인지 확인합니다.

 

범위 내에서의 소수판정법 (에라토스테네스의 체)

• 반복하면서 합성수를 소거하는 방식입니다.

 

과정

boolean[] nums = new boolean[N+1]; 
Arrays.fill(nums, true);

for (int i = 2; i <= N; i++) {
    if (!nums[i]) continue;    
    for (int j = i; j <= N; j*=2) nums[j] = false;
}

for (int k = 2; k <= N; k++) {
    if (nums[k]) answer.add(k);    	
}

return answer;

• 2부터 N까지 반복합니다.
• 현재 방문한 수의 배수를 소수가 아닌 수로 처리합니다.

 

2. 최대공약수

약수

• 어떤 수를 나누어 떨어지게 하는 수 입니다.

 

구현

 

• 약수끼리 곱이 N이 되게끔 짝을 지을 수 있습니다.

 

최대공약수란?

• 두 자연수의 공통된 약수 중에서 가장 큰 약수를 뜻합니다.

 

구현 (유클리드 호제법)

int gcd(int a, int b) {
     return a == 0 ? b : gcd(b % a, a);
}

• 두 수 A, B에 대해 A를 B로 나눈 나머지를 r이라 하면, GCD(A, B) == GCD(B, r) 입니다.

 

 

출처

• BaaaaaaaarkingDog - 수학