문제
a 이상 b 이하 범위 안의 수 중 소수인 것을 모두 찾아 총 합과 최솟값 구하기
실행 결과
코드(c++)
#include <iostream>
using namespace std;
/* 소수가 맞는지 확인하는 함수 */
bool isPrime(int n) {
if (n <= 1)
return false;
for (int i = 2; i * i <= n; i++) {
// 2부터 n-1까지의 자연수 중 n의 약수가 있는지 확인
if (n % i == 0)
return false;
}
return true;
}
int main() {
int a, b;
bool truePrime = false; // 소수인지 아닌지 판별 용 변수
int sum = 0; // 범위 내 소수의 합을 저장하기 위한 변수
int minPrime = -1; // 찾은 소수 중 가장 작은 소수를 저장
cin >> a >> b;
for (int i = a; i <= b; i++) {
if (isPrime(i)) {
truePrime = true;
sum += i;
if (minPrime == -1 || i < minPrime)
minPrime = i;
}
}
if (truePrime) {
cout << sum << "\n";
cout << minPrime << "\n";
} else {
cout << -1 << "\n";
}
return 0;
}
코드 설명
소수는 1과 자기 자신만을 약수로 가지는 함수이다.
따라서 2부터 해당 숫자까지 자기 자신으로 나누었을 때 나누어 떨어지는 수가 있다면 소수가 아니다.
반대로, 이에 해당하지 않는다면 소수에 해당하는 것이다.
이를 바탕으로 isPrime 함수를 작성한다.
문제에서 요구하는 것이 범위 내에서 소수에 해당하는 수를 모두 찾고,
이들의 sum과 그 중 최솟값을 찾는 것이므로 minPrime 변수를 선언한다.
truePrime 변수를 통해 범위 내에 소수가 없다면 -1만을 출력하게 한다.
만약 소수가 있다면, 반복문을 돌면서 소수를 sum에 더할 수 있다.
최솟값인 minPrime의 경우, 해당 반복문을 돌면서 수행하게 되는데
1. 아직 소수를 찾지 못한 경우, 즉 첫번째로 저장하는 경우
2. 저장된 최솟값보다 더 작은 경우
위 두 가지 경우에 대해서 작동하므로 해당 변수에 최솟값을 저장하게 된다.
최근 컴퓨터 보안 과목에서 소수에 대해 배웠는데,
코딩 테스트 공부도 덤으로 해보면서 공부해볼 수 있는 시간이 되어서 좋았다😊
문제 출처:
'PS' 카테고리의 다른 글
백준 1924번: 2007년 (0) | 2024.04.21 |
---|---|
코드트리: 1시간 뒤 시간 출력 (c++) (0) | 2024.04.19 |
백준 5597번: 과제 안 내신 분..? (0) | 2024.03.15 |
백준 10828번: 스택 (0) | 2023.03.25 |
백준 런타임에러(InsufficientSpace)는 언제 발생할까? (0) | 2023.03.23 |