[C 언어] 백준 2581. 소수

---

2581. 소수 (누르면 해당 문제로 이동)

소수를 찾는 문제 2

 

제약사항)

시간 : 1 초

메모리 : 128 MB

 

문제)

자연수 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을 출력한다.

 

입출력 예제

입력	출력
60 100	620 61
64 65	-1

 

---

 

풀이 순서)

1. 앞의 문제와 비슷한 문제로, 앞의 문제에서 for문의 범위만 바꾸어 소수인지 확인했습니다.

2. 소수라면 sum 변수에 그 값을 더하며, 소수일 때 sum 값이 0이라면 최초의 소수이므로 min 변수에 그 값을 저장합니다.

3. 소수의 합(sum)과 최솟값(min)을 출력하고, 소수가 없을 경우에는 -1을 출력합니다.

 

---

 

소스코드 및 결과 (C)

#include <stdio.h>

int main(){
	int M, N, i, j;
    int min, flags, sum=0;
    
    scanf("%d", &M);
    scanf("%d", &N);
    
    for( i=M ; i<=N ; i++ ){
    	flags=0;
        if( i==1 )
        	continue;
            
        for(j=2 ; j<i ; j++ )
        	if( i%j==0 )
            	flags=1;
                
        if( flags==0 ){
        	if( sum==0 )
            	min=i;
            sum += i;
        }
    }
    
    if( sum==0 )
    	printf("-1\n");
    else
    	printf("%d\n%d\n", sum, min);
    
	return 0;
}

 

메모리 : 1112 KB

시간 : 168 ms

코드길이 : 403 B

 

 

---