Notice
Recent Posts
Recent Comments
Link
great minds think alike
[C] 백준 BEAKJOON 1978번: 소수 찾기 본문

[C] 백준 BEAKJOON 1978번: 소수 찾기
https://www.acmicpc.net/problem/1978
1978번: 소수 찾기
첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.
www.acmicpc.net
[1] 문제

[2] 정답 및 해석
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void) {
int N;
int i;
int j;
int a[100];
int cnt = 0;
scanf("%d", &N);
for (i = 0; i < N; i++) {
scanf("%d", &a[i]);
}
for (i = 0; i < N; i++) {
for (j = 2; j <= a[i]; j++) {
if (a[i] % j == 0)
if (a[i] == j) {
cnt++;
break;
}
else
break;
}
}
printf("%d", cnt);
return 0;
}
scanf 를 통해 입력받은 값을 배열에 저장하고,
다시 배열의 요소를 불러와서 소수인지 검사하는 방법으로 알고리즘을 짰다.
[3] 풀이 과정 및 오답
# 첫 번째 시도 - 오답
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void) {
int N;
int i;
int j;
int a[100];
int cnt = 0;
scanf("%d", &N);
for (i = 0; i < N; i++) {
scanf("%d", &a[i]);
}
for (i = 0; i < N; i++) {
for (j = 2; j <= a[i]; j++) {
if (a[i] % j == 0) {
cnt = cnt + 1;
}
}
}
printf("%d", cnt);
return 0;
}
위의 코드는 문제가 있다.
현재 코드는 모든 수에 대해 2부터 a[i]까지 나누어 보면서 나누어 떨어지는 경우 cnt를 증가시킨다.
그러나 이렇게 하면 소수가 아닌 수들도 여러 번 나누어지기 때문에 올바른 소수 판별이 이루어지지 않는다.
소수 판별 알고리즘은 개선되어야 한다...
[4] 정답 제출


고친 풀이로 제출한 결과 정답!
[5] 느낀 점
소수 판별 알고리즘은 자주 쓰이는 것 같다.
학교 전공 중에 '컴퓨터 알고리즘'이라는 수업을 듣는데 생각보다 수업 내용이 도움이 많이 됐다.
차분하게 단계적으로 생각하게 해준 것 같다.
for 문에서 i 변수를 사용할 때, 범위를 설정해주는 부분에서 실수가 잦다. 배열과 엮이니 더욱 헷갈린다.
'SWLUG > 백준 BEAKJOON' 카테고리의 다른 글
[C] 백준 BEAKJOON 2164번: 카드2 (0) | 2023.09.27 |
---|---|
[C] 백준 BEAKJOON 10773번: 제로 (0) | 2023.09.20 |
[python/파이썬] 백준 BEAKJOON 10869번: 사칙 연산 (0) | 2023.06.25 |
[python/파이썬] 백준 BEAKJOON 1463번: 1로 만들기 (0) | 2023.06.25 |
[python/파이썬] 백준 BEAKJOON 2562번: 최댓값 (0) | 2023.06.25 |