0과 1의 쉼터

풀이 약수가 모두 주어지므로 가장 작은 약수와 가장 큰 약수의 곱이 N이다. 소스코드 #include int main(){ int N, val, max, min; scanf("%d", &N); for (int i = 0; i max && (max = val); val < min && (min = val); } printf("%d", max*min); } 출처 1037번: 약수 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, ..

문제 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수가 몇 개 있는지 출력한다. 입력 첫째 줄에 두 정수 min과 max가 주어진다. 출력 첫째 줄에 min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수의 개수를 출력한다. 제한 1 ≤ min ≤ 1,000,000,000,000 min ≤ max ≤ min + 1,000,000 풀이 문제에서 주어진 "제곱 ㄴㄴ 수"는 수론에서 제곱 인수가 없는 정수(Square-free Integer)로, 1이 아닌 제곱수를 인수로 지 않는 양의 정수이다. 쉽게 정수에 대해 소인수분해를 했을 때 동일한 글에서..

풀이 "백준 1978 소수 찾기"문제와 유사하다. 단, 1은 소수가 아니다 arr[0] = 0으로 초기화해주자. 소스코드 #include #include #define MAX 1000000 int arr[MAX]; int main(){ int idx = 3; for (int i = 0; i < MAX; i++) arr[i] = i+1; for (int i = 2; i

풀이 입력받은 수 num이 num/2 이하의 범위 중에 소수가 존재하는지 몇 줄 내로 간단하게 해결할 수 있지만, 에라토스테네스의 체를 이용해 효율적으로 풀이해봤다. 에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 발견한 소수를 구하는 알고리즘이다. N까지의 수는, N의 제곱근보다 작은 정수들의 배수를 모두 지우고 남는 수가 소수라는 사실을 알 수 있다. 이번 문제에서 주어지는 최대의 자연수는 1000으로, 1000의 제곱근인 31.62xxx보다 작은 정수 31까지의 배수들을 제외하고 남은 수들이 소수임을 알 수 있다. 하지만, 문제에서 입력받는 수가 소수인지 확인하기 위해 탐색하는 과정이 효율적이지 못해 위에서 조작한 배열을 소수와 소수가 아닌 구간으로 정렬해주었다. int arr[MAX], ..

풀이 유클리드 호제법은 최대공약수를 구하는 알고리즘이다. 두 수 N, M (N > M)을 입력받는다. N을 M으로 나누었을 때의 몫과 나머지가 N, M이 되며 이 과정을 나머지가 0이 될 때 까지 반복한다.\ 나머지가 0이 될때의 N(몫)이 최대공약수이다. 두 수 N, M의 곱은 최대공약수(GCD)와 최소공배수(LCM)의 곱과 같다. 소스코드 #include int euclidean_gcd(int n, int m){ return m ? euclidean_gcd(m, n%m) : n; } int main(){ int n, m; scanf("%d %d", &n, &m); int gcd = euclidean_gcd(n, m); printf("%d\n%d", gcd, n*m / gcd); } 출처 및 참고자료 ..