안녕하세요 박민성입니다.
오늘은 백준 1929번 소수 구하기를 풀어 보겠습니다.
문제를 보면 간단합니다.
입력은 첫째 줄에 1보다 크거나 같고 1,000,000보다 작거나 같은 M과 N이 공백을 두고 주어집니다.
출력은 주어진 M과 N사이에 있는 소수들을 한 줄씩 출력하면 끝입니다.
일단은 M과 N을 각각 a와 b에 입력을 받아옵니다.
그러고 for문을 사용하여 a와 b 사이에 수가 소수인지 체크하기 위해 can이라는 bool 변수와 만약 입력에 1이 들어오면 1은 소수가 아니니 continue로 검사를 하지 않고 다음 수로 넘어갑니다.
그리고 이중 for문을 이용하여 i가 소수인지 아닌지 체크합니다.
체크 방법은
에라토스테네스의 체
Sieve of Eratosthenes 고대 그리스의 수학자 에라토스테네스 가 만들어 낸 소수 를 찾는 방법.
namu.wiki
에라토스테네스의 체를 참고했습니다.
그리하여 j는 2부터 시작하고 MathF에 Sqrt를 사용하여 들어온 수의 제곱근까지 반복하는 for문입니다.
i % j가 만약 0이면 약수가 1과 자기 자신의 수 말고 더 있는 것이니 소수가 아닙니다. 그래서 can을 false로 만들고
마지막에 can을 체크하여 소수면 i를 출력 아니면 출력을 하지 않도록 합니다.
이것이 전체 코드입니다.
하지만 이대로 백준에 제출하면 시간초과가 뜹니다.
왜냐하면 Console.WriteLine는 for문으로 계속 호출하는 것은 시간 등등 여러 가지로 안 좋기 때문입니다.
그래서
StringBuilder를 사용하여 한번에 출력해 주었습니다.
이렇게 백준에 제출하였더니
정답이었습니다.
'알고리즘 C#' 카테고리의 다른 글
| 백준 1735번 분수 합 C#으로 문제 풀어보기 (0) | 2025.10.18 |
|---|---|
| 백준 2164번 카드2 C#으로 문제 풀어보기 (0) | 2025.10.16 |
| 백준 10815번 숫자 카드 C#으로 문제 풀어보기 (0) | 2025.09.24 |
| 백준 1316번 그룹 단어 체커 C#으로 문제 풀어보기 (0) | 2025.09.13 |
| ★백준 1920번 수 찾기 C#으로 문제 풀어보기★ (1) | 2025.08.24 |