[Baekjoon/백준]단계별로 풀어보기 9단계: 기본 수학 2-1번~3번(C/C++)

백준 단계별로 풀어보기 9단계: 기본 수학 2

https://www.acmicpc.net/step/10

기본 수학 2 단계

---

(1) 백준 1978번: 소수 찾기

https://www.acmicpc.net/problem/1978

1978번: 소수 찾기

• 문제 설명

   -주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

• 입력과 출력

   -입력: 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

   -출력: 주어진 수들 중 소수의 개수를 출력한다.

• 코드

#include <stdio.h>

int main() {
	int N, M, count = 0, isPrime;
	scanf("%d", &N);

	for (int i = 0; i < N; i++) {
		scanf(" %d", &M);
		isPrime = 0;

		if (M == 1)
			continue;

		for (int j = 2; j < M; j++)
			if (M % j == 0)
				isPrime = 1;

		if (isPrime == 0)
			count++;
	}

	printf("%d\n", count);

	return 0;
}

• 결과

백준 제출 결과

---

(2) 백준 2581번: 소수

https://www.acmicpc.net/problem/2581

2581번: 소수

• 문제 설명

   -자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오.

    예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다.

• 입력과 출력

   -입력: 입력의 첫째 줄에 M이, 둘째 줄에 N이 주어진다.

    M과 N은 10,000이하의 자연수이며, M은 N보다 작거나 같다.

   -출력: M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다.

    단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.

• 코드

   -최초 작성 코드(시간 초과로 실패..)

#include <stdio.h>

int main() {
	int M, N, temp, isPrime, sum = 0, min = 0, count = 0;
	scanf("%d", &M);
	scanf("%d", &N);

	temp = M;

	while (!(temp > N)) {
		if (temp == 1)
			continue;

		isPrime = 0;

		for (int i = 2; i < temp; i++)
			if (temp % i == 0)
				isPrime = 1;

		if (isPrime == 0) {
			if (count == 0)
				min = temp;

			sum += temp;
			count++;
		}

		temp++;
	}
	

	if (count == 0)
		printf("-1\n");
	else
		printf("%d\n%d\n", sum, min);

	return 0;
}

   -완성 코드

#include <stdio.h>

int main() {
	int M, N, temp, isPrime, sum = 0, min = 0;
	scanf("%d", &M);
	scanf("%d", &N);

	for (temp = M; temp <= N; temp++) {
		if (temp == 1)
			continue;

		isPrime = 0;

		for (int i = 2; i < temp; i++)
			if (temp % i == 0)
				isPrime = 1;

		if (isPrime == 0) {
			if (sum == 0)
				min = temp;
			sum += temp;
		}
	}
	
	if (sum == 0)
		printf("-1\n");
	else
		printf("%d\n%d\n", sum, min);

	return 0;
}

• 결과

백준 제출 결과

---

(3) 백준 11653번: 소인수분해

https://www.acmicpc.net/problem/11653

11653번: 소인수분해

• 문제 설명

   -정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

• 입력과 출력

   -입력: 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

   -출력: N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

• 코드

#include <stdio.h>

int main() {
	int N;
	scanf("%d", &N);

	if (N != 1){
		for (int i = 2; i <= N; i++)
			while (N % i == 0) {
				printf("%d\n", i);
				N /= i;
			}
	}

	return 0;
}

• 결과

백준 제출 결과