본문 바로가기

CS/Algorithm3

[Algorithm] 약수 구하기 for(int i = 1; i 2022. 11. 18.
[Algorithm] 에라토스테네스의 체 에라토스테네스의 접근 주어진 자연수 N이 소수이기 위한 필요충분 조건은 N이 N의 제곱근보다 크지 않은 어떤 소수로도 나눠지지 않는다. 소수가 되는 N이 자연수라면 sqrt(N)보다 작은 수로 나눠지지 않음 1, 2, 4, 5, 8, 10, 16, 20, 40, 80 자연수 N : 80, sqrt(80) : 8.xxxx, 2부터 8.xxxx이하만 검색하면 이후의 값은 검사할 필요가 없음 1-80, 2-40, 4-20, 5-16, 8-10이기 때문에 8.xx이하만 검사하면 됨 bool IsPrime(int num) { for (int i = 2; i * i 2022. 11. 14.
[Algorithm] 유클리드 알고리즘 (GCD) 유클리드 알고리즘 - 주어진 두 수 사이에 존재하는 최대 공약수 (GCD) 구하는 알고리즘 - 자세한건 유클리드 호제법 참고 - gcd ( a, b ) == gcd ( b, r ) 이다. (a,b 자연수 / r은 a를b로 나눈 나머지) 원리 자연수 a, b가 주어짐 이때 a가 b보다 큰 값임 int a = 자연수 int b = 자연수 a 를 b로 나눈 나머지가 r 이면 int r; r = a % b; r이 0이면 b가 최대 공약수(gcd) 이다. if (r == 0) return b; 만약 r이 0이 아니면, a에 b값 넣고, b에 r값 넣고, 다시 두번째 부터 반복하면 된다. while(1){ int r = a % b; if( r == 0 ) return b; a = b; b = r; } 공식 int .. 2022. 10. 17.

티스토리툴바