시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
| 2 초 | 256 MB | 263704 | 77331 | 54397 | 27.358% |
문제
M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
출력
한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.
풀이✔
1️⃣ 문제 분석하기
- M이상 N이하의 소수를 출력하는 프로그램을 작성 해야함
- 소수가 무엇인지를 알아야함
- 소수란, 나누었을 때 몫이 자신 숫자와 1만 있는 것을 의미함.
2️⃣ 요구 조건 구현하기
- Bufferedreader 생성
- StringTokeinzer 생성
- int N, int M = StringTokeinzer 로 입력받기
- 소수를 출력하는 로직 작성하기
- N~M까지의 숫자 중에서 소수를 찾아야함.
3️⃣ 슈도 코드
Bufferedreader 생성
StringTokeinzer 생성
int N = StringTokeinzer 입력받기
int M = StringTokeinzer 입력받기
N~M 까지 범위에서 소수를 찾는 로직을 찾아야함.
for문(i=N; i<=M; i++;) {
조건을 줘서 찾는다.
}
4️⃣ 코드 작성
package Algorithm_step;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class B1929 {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
for (int i = N; i <=M ; i++) {
if(isPrime(i)) {
System.out.println(i);
}
}
}
private static boolean isPrime(int num) {
if(num<2) {
return false;
}
for (int i = 2; i*i <=num ; i++) {
if(num%i==0) {
return false;
}
}
return true;
}
}
- 1,2 미만의 숫자는 소수가 아니기 때문에 예외 조건을 주고 시작합니다.
- 2부터 num의 제곱근 까지의 숫자로 나눈다.
- 여기서 조건을 준다 나누어 떨어지는 숫자가 있다면 소수가 아니다.
- 로직을 보면은 num이 3일 때 부터 16일 때를 확인해 봅니다.
- num = 3
i=2, 2*2 ≤ 3; i++ ← 조건을 만족하지 않는다
if문 거치지 않고 true닌까 위로 리턴 한다.
- num = 4
i=2 , 2*2 ≤ 4; i++ ← 조건 만족
if문 안으로 들어감.
4 % 2 ==0 조건 만족하므로 false 리턴
return false;는 해당 함수를 종료하고 함수를 호출한 곳으로 false를 반환합니다. 함수 내부의 나머지 부분은 실행되지 않습니다.
위 부분을 모르고 있어 문제를 이해하는데 어려움을 많이 겪었습니다.. 하
- num = 5
i=2, 2*2 ≤5 i++ ← 조건 만족
if문 조건 확인
5%2 == 0 → false이므로 return false가 실행되지 않는다.
i가 3일 때 i * i <= num이 만족하지 않으므로
for문을 빠져나와서 return true를 발생시켜 호출함수로 보낸다.
5️⃣ 궁금한 점
위 로직에서 조건을 줄 때
i * i <= num;
왜 이렇게 주는지가 궁금했습니다.
ChatGPT 말로는
- 효율성 측면:
- i * i <= num 조건은 **i**를 증가시키며 제곱한 값이 **num**보다 작거나 같은 동안 루프를 돌립니다.
- 만약 **num**이 소수가 아니라면, 즉 어떤 수 **a**와 **b**가 곱하여 **num**이 되는 경우, 반드시 a 또는 **b**는 **num**의 제곱근 이하의 값이 됩니다.
- 따라서 **i**를 제곱하여 **num**보다 큰 값이 되는 경우에는 더 이상 확인할 필요가 없습니다.
- 성능 개선:
- **i * i**는 제곱을 계산하는 것이므로 일반적으로 **i * i**보다 **i * i <= num**를 사용하는 것이 성능 면에서 더 효율적입니다.
- 제곱근을 사용하지 않고도 정수 간의 비교만으로 판별할 수 있습니다.
예를 들어 **num**이 25라면, 25의 제곱근은 5입니다. **i * i**를 계산하는 대신 **i * i <= num**로 비교하면, **i**가 6 이상이 될 때 루프가 종료됩니다.
이렇게 설명을 해주었는데 납득이 되지않아
그냥 소수 구하는 로직을 통째로 외워버리기로 했습니다.
외우다 보면 자연스럽게 이해가 될 것이라고 생각합니다.
6️⃣ 핵심 파악하기
- 소수 → 자신과 1만으로만 나누어 지는 숫자.
- 소수를 구하는 알고리즘이 있는데 그것은 사용하지 않았음
- 효율을 추구한다면 → 에라토스테네스의 체 알고리즘 알아야함.