코드트리: 소수 (c++)

 

 

 

---

 

 

문제

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. 저장된 최솟값보다 더 작은 경우

위 두 가지 경우에 대해서 작동하므로 해당 변수에 최솟값을 저장하게 된다.

 

최근 컴퓨터 보안 과목에서 소수에 대해 배웠는데, 

코딩 테스트 공부도 덤으로 해보면서 공부해볼 수 있는 시간이 되어서 좋았다😊

 

---

문제 출처: 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석