코딩하는 냄뚜

에라토스테네스의 체 - 소수를 쉽게 구하는 체(거름망) 그림으로 알아보자. 우선 숫자를 100까지 써본다. 그 후 각 숫자에 따라서 그 수의 배수인 수들은 모두 제거해나가기 시작한다. 2를 고르고, 2의 배수를 모두 지우고, 3을 고르고 3의 배수를 모두 지우고, 4는 2의 배수로 지워져있기 때문에 4의 배수는 다시 지우지 않아도 된다. 이렇게 지워지고 남은 수들은 모두 소수이다. 왜냐면 자기 자신과 1을 곱해야 나오는 수이기 때문이다. 100이 소수인지 확인하기 위해서 일일이 100보다 작은 모든 수들로 확인할 필요는 없다. 이 방식대로 하면 시간복잡도가 O(n^2)이 되어버리고 소수인지 판별하려는 숫자가 너무 커지게 되면 코드 실행 시간이 매우 커지게 될것이다. 하지만, 소수인지 확인하려는 수의 제곱..

최대공약수(Great Common Divisor / GCD) 어느 수들의 공통된 약수중 가장 큰 약수를 최대 공약수라고 한다. int a, b; int r=a%b; int g; //g는 최대공약수 gcd(a,b)=gcd(b,r); if(r==0){ g=b; } ////재귀함수를 사용한 유클리드 호제법 구현 int gcd(int x, int y){ if(b==0){ return a; }else{ return gcd(b, a%b); } } ////재귀함수를 사용하지 않는 유클리드 호제법 구현 int gcd(int a, int b) { while(b!=0) { int r=a%b; a=b; b=r; } return a; } 최소 공배수(Least Common Multiple/LCM) 어느 수들의 공통된 배수 중..