알고리즘/백준
백준 1929번 소수 구하기 / 백준 단계별로 풀어보기 8단계 / 8. 기본 수학 2
김발자~
2022. 9. 18. 19:55
반응형
백준 8단계 4번 문제 - 1929 소수 구하기
https://www.acmicpc.net/problem/1929
1929번: 소수 구하기
첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
www.acmicpc.net
8. 기본 수학 2 (4) 백준 1929번 문제 소수 구하기
문제

과정 생각해보기
2581번 문제를 응용해서 풀어보기로 했다
sum이랑 min을 구했던 자리에 println문만 해주면 나올 때마다 반복될 것
정답 인정 코드
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
|
import java.util.Scanner;
public class Main {
public static boolean prime[];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
int n = sc.nextInt();
prime = new boolean[n + 1];
get_prime();
for(int i = m; i <= n; i++) {
if(prime[i] == false) { //false = 소수
System.out.println(i);
}
}
}
public static void get_prime() {
prime[0] = true;
prime[1] = true; //0과 1은 소수가 아니다
for(int i = 2; i <= Math.sqrt(prime.length); i++) {
for(int j = i * i; j < prime.length; j = j + i) { //i 배수들 거르기
prime[j] = true;
}
}
}
}
|
cs |
2581번보다 오히려 간단해진 코드
직후 백지 복습

복습하면서 까먹었던 부분들 표시
2581에선 이해하지 못했던 것들이 한 번 더 해보니까 그때보단 발전한 것 같다
8단계는 전 단계에서 배운 걸 응용하는 느낌이라 그런지 더 뿌듯하고 재밌다
반응형