728x90
반응형
소수
문제
자연수 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을 출력한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
#include <stdio.h>
int main()
{
int M,N;
int sum = 0;
int flag = 0;
int min = 0;
scanf("%d\n%d",&M,&N);
for(int i=M; i<=N; i++){
flag = 0;
if(i==1) continue;
for(int j=2; j<i; j++){
if(i%j==0) flag = 1;
}
if(flag==0){
if(sum==0) min = i;
sum +=i;
}
}
if(sum ==0) printf("-1\n");
else{
printf("%d\n%d",sum,min);
}
return 0;
}
|
cs |
M이상 N이하의 소수를 찾아야 한다.
1. 소수 찾기
2. 소수들의 합 구하기
3. 소수 중 최소값 구하기
소수는 for 문을 통해서 찾을 수 있다.
flag 변수를 이용해서 2부터 i 까지 나눠떨어지는 수가 있으면 flag = 1
그렇지 않으면 flag = 0 으로 유지한다. flag 가 0 일때만 i 가 소수이다.
flag =0 일때, sum변수에 += i 한다.
소수인 경우에만 더하므로 소수들의 합 역시 구할 수 있다.
가장 작은 소수는 M부터 N까지의 순서대로 찾을 때,
가장 먼저 찾게 되는 소수 일 것이고, 가장 먼저 찾을 때의 sum 값은 0일 것이다.
즉, sum =0 일때 찾은 flag = 0 인 i 값이 가장 작은 소수인 min 값이다.
반응형
'백준 단계별로 풀어보기 > 기본 수학 2' 카테고리의 다른 글
| 백준 1978 소수 찾기 (0) | 2022.09.19 |
|---|