소수 인지 체크하는 함수 와 최대공약수, 최소 공배수 구하기

소수 인지 체크

어떤수가 소수인지 체크 하기 위해서 2부터 검사값까지 모두 나누어 보면서 나누어 떨어지는 수가 있는지 찾아보면 되지만 2부터 루트(검사값)까지만 모두 나누어 봐도 알수 있다.

 

public static boolean check(int n) {
     if(n==1)
        return false;
    
     for(int i=2;i<=Math.sqrt(n);i++) {
       if(n%i==0) {
         return false;
       }
  
     }
     return true;

}

 

최대공약수 , 최소 공배수 

유클리드호제법을 이용해서 구함

유클리드 호제법 : 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

 

int r=1;

val1 은 큰수 val2 는 작은수

while(r>0){

           r = val1 % val2;

           val1 = val2;

           val2 = r;

}

LCM = tmp1 * tmp2 / val1; // 최소 공배수