🔗 백준 1929 소수 구하기 https://www.acmicpc.net/problem/1929
문제
M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
출력
한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.
풀이
M 이상 N 이하의 소수를 구하는 문제였다.
소수는 자기 자신과 1만을 약수로 갖는 수를 말하기에 0, 1은 무조건 제외된다.
그리고 제곱근을 사용하여 시간을 절반으로 줄여주었다.
제곱근을 기준으로 앞 수와, 뒤의 수는 짝을 이루기 때문에 앞에 수들로 나누어 떨어지면 뒤의 수들도 무조건 나누어 떨어진다.
즉, 제곱근 기준 앞의 수들만 검사하면 된다는 이야기이다.
에라토스테네스의 체 를 활용한 소수 구하기도 있다고 하였지만 아직 적용해보진 못하였다.
추후 공부하여 블로깅하겠다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
int n = sc.nextInt();
for (int i = 0; i <= n; i++) existPrime(i, m);
}
private static void existPrime(int num, int m) {
if (num < 2) return;
for (int i = 2; i <= Math.sqrt(num); i++) {
if (num % i == 0) return;
}
if (num >= m) System.out.println(num);
}
}