백준 - 단계별로 풀어보기/약수, 배수와 소수

1. 문제 상세 https://www.acmicpc.net/problem/11653 2. 문제 접근 입력받은 수를 소인수분해 하는 과정을 출력하자. 입력받은 수 N 을 1이 될 때 까지 2부터 N 까지의 수로 나누며 나눈 수를 출력한다. 주의할 점은 N 을 나누었을 때 나머지가 0이 아닐 경우에만 다음 수로 나눠야한다는 것이다. 예를 들어서 N 이 12인 경우를 보자. 12를 2로 나눌 경우 나머지가 0이기 때문에 2로 나눠서 N 은 6이 되고 2를 출력한다. 6을 2로 나누면 나머지가 0이기 때문에 6을 2로 나눠서 N 은 3이 되고 2를 출력한다. 3은 2로 나누었을 때 나머지가 0이 아니기 때문에 2 다음인 3으로 나눠보자. 3을 3으로 나누면 나머지가 0이기 때문에 3으로 나눠 N 은 1이 되고 ..

1. 문제 상세 https://www.acmicpc.net/problem/2581 2. 문제 접근 주어진 수 M 부터 N 까지의 자연수 중 소수를 찾자. 범위 내의 소수를 찾기 위해 에라토스테네스의 체 알고리즘을 사용하여 문제를 해결해보자. ■ 에라토스테네스의 체 에라토스테네스의 체 알고리즘은 주어진 범위 내에서 소수들을 찾는데 효율적인 알고리즘이다. 2부터 주어진 수 까지의 수들 중 가장 작은 수의 배수부터 지워나간다. 가장 작은 수의 제곱이 주어진 수보다 작을 때 이 과정을 반복한다. 위 사진에서는 2부터 120까지의 수가 있다. 가장 먼저 2부터 120까지의 2의 배수가 모두 지워지고, 그 다음 3의 배수가 모두 지워진다. 그 다음 지워지지 않은 수 중 가장 작은 수인 5의 배수, 그 다음 7의 배..

1. 문제 상세 https://www.acmicpc.net/problem/1978 2. 문제 접근 소수는 자기 자신과 1만을 약수로 가지는 수이다. 입력받은 N 개의 숫자가 소수인지 확인하여 소수인 숫자의 개수를 알아내자. 일단 이를 위해 각 숫자가 소수인지를 확인해야 한다. 입력받은 숫자가 X 라고 하자, 이 X 가 소수인지 확인하기 위한 방법을 크게 3가지로 꼽아봤다. 1. X를 2부터 X - 1의 수까지 나누어 보며 나머지가 0이 아닌지 확인하는 방법이 있다. 하지만 이 방법은 2부터 X - 1 까지의 수를 전부 나누어 봐야 하기 때문에 연산 횟수가 많다. 2. X를 2 부터 X / 2 의 수까지 나누어 보며 나머지가 0이 아닌지 확인하는 방법이다. X를 나눌 때, X를 제외하고 X의 절반이 넘는 ..

1. 문제 상세 https://www.acmicpc.net/problem/9506 2. 문제 접근 완전수를 구하기 위해 입력받은 자연수 N 을 1부터 N / 2 의 수로 나누어보며 나눈 나머지가 0이 되는 경우의 수를 배열에 추가하고, N 과 비교할 완전수 변수에 더해준다. 모든 약수들을 확인하고 나면 입력받은 N 과 약수들을 모두 더해둔 값이 저장된 완전수 변수의 값이 같은지 확인한다. 값이 같다면 완전수이므로 배열에 추가해둔 약수들로 조건대로 출력하고, 아닌 경우도 해당 조건대로 출력한다. 3. 문제 풀이 #include using namespace std; int main() { int n, factor[50000]; while(true) { int perfect = 0, index = 0; cin..

1. 문제 상세 https://www.acmicpc.net/problem/2501 2. 문제 접근 for문을 사용하여 자연수 N 을 1부터 N 까지의 숫자로 나누어 가면서 나머지가 0인 경우에 카운트를 증가시킨다. 이렇게 약수를 구하며 카운트를 증가시키다가 입력받은 K 의 값과 같아지면 반복을 빠져나오고, 해당 수를 출력한다. 만약 N 까지의 수를 모두 나누어도 카운트가 K 와 같아지지 않았다면 0을 출력한다. 3. 문제 풀이 #include using namespace std; int main() { int n, k, i, count = 0; cin >> n >> k; for(i = 1; i

1. 문제 상세 https://www.acmicpc.net/problem/5086 2. 문제 접근 먼저 뒤의 수를 앞의 수로 나누어 나누어 떨어진다면 factor 를 출력한다. 아닌 경우 앞의 수를 뒤의 수로 나누어 나누어 떨어진다면 multiple 을 출력하자. 위의 경우가 모두 아닐 때 neither 를 출력한다. 무한 반복문을 통해 수를 계속 입력받고, 입력받은 두 수가 모두 0이면 루프를 빠져나오자. 3. 문제 풀이 #include using namespace std; int main() { int a, b; while(true) { cin >> a >> b; if(a == 0 && b == 0) break; else if(b % a == 0) cout