여러가지 수학

 

나머지 연산:

(a+b)%m = ((a%m)+(b%m))%m

(a*b)%m = ((a%m)*(b%m))%m

(a-b)%m = ((a%m)-(b%m)+m)%m; //음수나머지 나올 수 있다 -> +m한번 해주면 양수로만 나옴

*C(JAVA)와 python 나머지 구하는 방식 차이 c와 java는 나머지를 버림, python은 내림을 이용한다.

 

-GCD,LCM

 

GCD -> 유클리드 호제법 O(logN)

//재귀호출
public int getGCD(int a, int b)
{	if(b == 0) return a;
	else return getGCD(b,a%b);
}

//반복문
pulbic int getGCD(int a, int b){
	while(b != 0){
    int r = a%b;
    a=b;
    b=r;
    }
}

 

N개의 수의 최대공약수 --> GCD(GCD(GCD(a,b),c),n).. 

LCM = a*b/GCD

 

소수찾기 

 

1.

public static boolean isPrime(int n){
    if(n<2) return false;

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

    return true;

2.

public static boolean isPrime(int n){
    if(n<2) return false;

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

    return true;
}

3.

public static boolean isPrime(int n){
    if(n<2) return false;

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

    return true;
}

-에라토스테네스의 체

boolean[] isNPrime = new boolean[M+1]; //isNotPrime -> 소수면 false 짝수면 true
int[] primeNumber = new primeNumber[M]; // 소수 저장
int index =0;
isNPrime[0] = isNPrime[1] = true; // 0과 1은 소수가 아니다.

//소수들 저장하고 싶을 때
for(int i=2; i<=M; i++){
    if(isNPrime[i] == false){
      primeNumber[index++] = i;
      for(int j= i+i ; j<=M; j+=i){
      isNPrime[j] = true;
      }
    }
}

//소수 index에 true false값 저장한 배열만 만들고 싶을 때
for(int i=2; i*i<=M; i++){  // i의 배수는 모두 지워짐 i*i가 M을 넘어서면 검사할 필요없다.
	if(isNPrime[i])continue; 
    for(int j= i+i ; j<=M; j+=i){ 
      isNPrime[j] = true;
      }
}

소수숫자를 저장하고 싶으면, i <= M의 조건식으로 i++하면서 해야겠지만, 그런게 아니라면,

i*i<= M의 (루트M 소수찾기 검사식)을 넣어도 된다. 왜냐면, 가령 M이 110이라고 해보자.

2의 모든 배수를 지우고나면, 3은 3*2가 이미 지워졌음으로 3*3부터 검사하면되고, 4는 4*4 ---> 10*10부터 검사하면된다 

그 전의 값들은 이미 그 밑의 수의 배수로 지워졌기 때문이다. 따라서 M이 110이면, 10*10까지만 검사하면되지 11은 어차피 11*11부터 검사할텐데 이는 121이라 어차피 M의 범위를 넘어가므로 검사할 필요가 없다.

 

-골드바흐 추측 -- > n = a+b --n-b도 소수 

-팩토리얼 0의 갯수 --> 어떤 소인수를 인자로 가지고 있는 수는 그 소인수의 배수..

 

-진법 변환 

보통 A진법에서 B진법으로 고치려면 (각각 한자리에 표현할 수 있는 수의 범위가 0~a-1, 0~b-1임) 

A진법을 -> 10진법으로 고치고 -> %B진법연산 뒤집으면 됨(스택이용하면 뒤집기 쉬움,o sb)

a="12345";
int baseA;
int baseB;
int Decimal;
StringBuilder sb;
//10진법으로 고치기
for(int i=0; i<a.length;i++)
{
	Decimal += Integer.parseInt(a.charAt(i))*Math.pow(baseA,a.length-1-i));
 	
}
//10 to B진법으로 전환
while( Decimal != 0){

	sb.append(Decimal % baseB);
    Decimal /= baseB;
}
sb.reverse();

 

2 <-> 8 , 2<->16은 비교적 더 간단함 

2진법 3칸  <-> 8진법 1칸  

2진법 4칸 <-> 16진법 1칸