[백준] 2581(소수) c언어

문제

자연수 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>
#include <stdlib.h>

//소수인지 판별
int func(int a) {

  int flag = 1;
  //1부터 a-1까지 for문 돌려서
  //나누어 떨어지면 소수아님 
  for(int i=2; i<a; i++) {
    if(a % i == 0) {
      flag = 0; //소수 아님 
      break;
    }
  }

  return flag;
}

int main(void) {
  //소수 합과 최소값 찾기 

  int n, m, sum = 0;
  scanf("%d\n%d", &n, &m);

  int *arr = calloc(sizeof(int), 10);
  arr[0] = 10001;

  for(int i=n; i<=m; i++) {
    if(i < 2) {
      continue;
    }
    else {
      if(func(i) == 1) { //소수일 때 
        sum+=i;
        if(arr[0] > i) {
          arr[0] = i;
        }
      }
    }
  }

  if(sum != 0) 
    printf("%d\n%d\n", sum, arr[0]);
  else
    printf("-1");
}

 

고려해야 할 점

1. 입력은 1부터 가능하나, 소수를 판별할 때는 2부터 가능하도록 한다.
2. m과 n은 10,000 이하의 수 이므로, 최소값을 설정할 때는 10001로 한다. 

 

끝!