[백준/JAVA] 1929번: 소수 구하기
🔺 문제
1929번: 소수 구하기
첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
www.acmicpc.net
🔺 코드
- 풀이1) int 배열 활용
|
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
31
32
33
34
35
36
|
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
int M = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
int[] A = new int[N + 1];
// 각 인덱스 값으로 초기화
for(int i = 2 ; i <= N ; i++) {
A[i] = i;
}
for(int i = 2 ; i <= Math.sqrt(N) ; i++) {
if(A[i] == 0)
continue;
// 배수 지우기
for(int j = i + i ; j <= N ; j += i) {
A[j] = 0;
}
}
StringBuilder sb = new StringBuilder();
for(int i = M ; i <= N ; i++) {
if(A[i] != 0) {
sb.append(A[i]).append("\n");
}
}
System.out.println(sb);
}
}
|
cs |
- 풀이2) boolean 배열 활용
|
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
31
32
33
|
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
int M = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
boolean[] isPrime = new boolean[N + 1];
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false;
// 배수 지우기
for(int i = 2 ; i <= Math.sqrt(N) ; i++) {
// 이미 체크된 배열이면, 다음 반복문으로 skip
if(!isPrime[i])
continue;
for(int j = i * i ; j <= N ; j += i)
isPrime[j] = false;
}
StringBuilder sb = new StringBuilder();
for(int i = M ; i<= N ; i++) {
if(isPrime[i]) {
sb.append(i + "\n");
}
}
System.out.println(sb);
}
}
|
cs |
✅ 해결 아이디어
✔ 소수 찾기 - 에라토스테네스의 체
💥 유의사항
⇨ 배수 지우는 부분 - 2번째 for문의 증감식 부분 j += i
⇨ i * i 미만의 변수는 이미 지워졌으므로 신경 안 씀.
🔺 다른 풀이들
백준 1929번 자바 문제 답/해설(소수 구하기 문제)
[1] 백준 카테고리 단계별로 풀어보기 기본 수학 2 4단계 1929번 문제 소수 구하기 [2] 문제 1. 입력 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소
engpro.tistory.com
[백준] 1929번 : 소수 구하기 - JAVA [자바]
https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.n
st-lab.tistory.com
💬 느낀 점
오랜만에 보는 에라토스테네스의 체 반갑
| 1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
| V | 6/12 | 6/20 |
(+6/12 2회독)
으아 오랜만에 혼자서 짜려니 또 까먹는다
이 망각의 곡선아,,,,ㅠ
|
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
|
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
StringBuilder sb = new StringBuilder();
int m = Integer.parseInt(st.nextToken());
int n = Integer.parseInt(st.nextToken());
boolean[] isPrime = new boolean[n + 1];
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false;
for(int i = 2 ; i <= n ; i++) {
if(isPrime[i]) {
for(int j = i + i ; j <= n ; j += i) {
isPrime[j] = false;
}
}
}
for(int i = m ; i <= n ; i++) {
if(isPrime[i]) sb.append(i).append("\n");
}
System.out.println(sb);
}
}
|
cs |
(+6/20 3회독)
boolean 배열로 소수 판별 배열을 만들었다.
|
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
|
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
StringBuilder sb = new StringBuilder();
int M = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
boolean[] A = new boolean[N + 1];
Arrays.fill(A, true);
A[0] = A[1] = false;
for(int i = 2 ; i <= (int)Math.sqrt(N) ; i++) {
for(int j = i * i ; j <= N ; j += i) {
A[j] = false;
}
}
for(int i = M ; i <= N ; i++) {
if(A[i]) {
sb.append(i).append("\n");
}
}
System.out.println(sb);
}
}
|
cs |
(참고)
✔ 에라토스테네스의 체 (boolean ver.)
[알고리즘] 소수(Prime Number) 구하기 - 에라토스테네스의 체 (Java)
소수 소수(prime number)는 정수론의 가장 중요한 연구 대상 중 하나로, 양의 약수가(1보다 큰 자연수) 1과 자기 자신만을 약수로 가지는 수를 의미한다. 소수의 반대말로, 세 개 이상의 양의 약수를
loosie.tistory.com
JAVA [자바] - 소수 구하는 알고리즘 및 구현
들어가기 전에 소수 [Prime Number] 소수의 정의는 1보다 큰 자연수 중 1 과 그 수 자기 자신만을 약수로 갖는 자연수를 의미한다는 점은 누구나 알고 있을 것이다. 즉, 소수의 약수는 2개만을 갖고,
st-lab.tistory.com