GCD

	public static int gcd(int a,int b){  //두 수를 입력 받음
        int r = 1; // 나머지 값

        while(b!=0){ //b가 0일때까지
            r = a % b; //a와 b를 나눈 나머지를 r에
            a = b; //a는 b의 값
            b = r;  //b는 r의 값
        }
        return a; //b기 0일때의 a가 최대공약수
    }

나머지 연산을 통해 b가 0일때 a의 값이 최소 공배수가 됩니다.

---

LCM

GCD를 활용하면 LCM을 쉽게 구할수 있습니다. 두 수를 곱한 수에서 최대 공약수를 나눠주면 최소 공배수입니다.(예: 6,8은 각각 6=2x3, 8=2x2x2이므로 gcd=2 이고 lcm=24이다. 6x8/gcd(2)는 lcm(24))

	public static int lcm(int a, int b){
        return a * b / gcd(a,b); //두 수를 곱한 값에서 gcd를 나눈다.
    }

---

소수 구하기

메모리(배열)을 이용하여 소수를 쉽고 빠르게 구할 수 있는 방법이 아리스토테네스의 체입니다. 의외로 이미 소수가 아님이 판정난 수들은 건너 뛰고 수가 커질 수록 생략되는 경우가 많기 때문에 시간복잡도가 낮은편입니다.(메모리는 많이 먹지만)

일반적인 소수 구하기

public boolean isPrime(int N){
	for(int i = 2; i <= N/2; i++){
    	if(N % i == 0) return false;
    }
    return true;
}

2부터 N/2까지의 수 i중에서 N과 나누어 떨어지는 수가 존재하면 소수가 아니고 하나도 존재하지 않으면 소수임을 알 수 있습니다.

몇십만의 수가 소수인지 판별하려면 몇십만번의 for루프를 돌아야 하고 하나의 수가 아닌 여러 수를 소수 판별할땐 기하급수적으로 늘어날 수 있습니다.

아리스토테네스의 체

public boolean[] Prime(int N){
    
    boolean[] 소수아닌수 = new boolean[N+1];
    
    소수아닌수[0] = true;
    소수아닌수[1] = true;
    
    for(int i=2;i<=N;i++){
    	if(소수아닌수[i]) continue;
        
        for(int j=i*2; j<=N;j+=i){
        	소수아닌수[j] = true;
        }
    }
    
    return 소수아닌수;
}

소수아닌수라는 배열에 소수여부가 저장되어 한번만 소수를 계산하면 계속 사용할 수 있습니다. 0과 1은 항상 소수가 아니고, 소수가 아니면 건너뛰기, 소수면 배수들은 모두 소수가 아닌 수가 됩니다.