[백준] 1929 : 소수 구하기 - JAVA

🙋🏻‍♀️에라토스테네스의 체 이용!

문제분석

M이상 N이하 사이의 숫자 사이에 소수를 구하는 문제이다.
N의 최대범위가 1,000,000이기때문에 일반적으로 제곱근범위까지 나누어보면서 소수를 구하는 방법은 O(sqrt(10^6) * 1,000,000) = O(10^9)이다. 따라서 시간제한 2초안에 해결하기 힘드므로, 에라토스테네스의 체를 이용한다.

---

Troubleshooting

public class Main {
static int N;
static int M;
static ArrayList<Integer> A;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		M = sc.nextInt();
		N = sc.nextInt();
		A = new ArrayList<>();
		for(int i=M; i<=N; i++) {
			A.add(i);
		}
		if(A.contains(1)) A.remove(Integer.valueOf(1));
		primeNumber();
		for(int i=0; i<A.size(); i++) {
			System.out.println(A.get(i));
		}
	}
	public static void primeNumber() {
		for(int i : A) {
			for(int j=2; i*j<=N; j++) {
				A.remove(Integer.valueOf(i*j));
			}
		}
	}
}

문제

ConcurrentModificationException가 발생했다.

원인

보통 리스트나 Map 등, Iterable 객체를 순회하면서 요소를 삭제하거나 변경을 할 때 발생한다고 한다.
ArrayList를 순회하며, 특정 요소를 삭제하기 때문에 발생하는것으로 보인다.

해결

삭제할 원소를 담은 배열을 따로 만들어서, 해당 배열에 삭제할 원소들을 넣어두고, 한번에 삭제한다.

Troubleshooting 2

public class Main {
static int N;
static int M;
static ArrayList<Integer> A;
static ArrayList<Integer> removed;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		M = sc.nextInt();
		N = sc.nextInt();
		A = new ArrayList<>();
		removed = new ArrayList<>();
		for(int i=M; i<=N; i++) {
			A.add(i);
		}
		if(A.contains(1)) A.remove(Integer.valueOf(1));
		primeNumber();
		for(int i=0; i<A.size(); i++) {
			System.out.println(A.get(i));
		}
	}
	public static void primeNumber() {
		for(int i : A) {
			for(int j=2; i*j<=N; j++) {
				if(!removed.contains(i*j)) {
					removed.add(i*j);
				}
			}
		}
		for(int k : removed) {
			A.remove(k); // error 발생지점
		}
		
	}
}

문제

java.lang.IndexOutOfBoundsException: Index 12 out of bounds for length 12 가 발생했다.

원인

remove(k) 를 쓰면, k가 인덱스로 인식된다.

해결

나는 특정 값을 삭제하려고 remove를 사용했기때문에, remove(Integer.valueOf(k))를 써야한다.

Troubleshooting 3

import java.util.Scanner;
import java.util.ArrayList;

public class Main {
static int N;
static int M;
static ArrayList<Integer> A;
static ArrayList<Integer> removed;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		M = sc.nextInt();
		N = sc.nextInt();
		A = new ArrayList<>();
		removed = new ArrayList<>();
		for(int i=M; i<=N; i++) {
			A.add(i);
		}
		if(A.contains(1)) A.remove(Integer.valueOf(1));
		primeNumber();
		for(int i=0; i<A.size(); i++) {
			System.out.println(A.get(i));
		}
	}
	public static void primeNumber() {
		for(int i : A) { // 출력초과 발생원인 지점 
			for(int j=2; i*j<=N; j++) {
				if(!removed.contains(i*j)) {
					removed.add(i*j);
				}
			}
		}
		for(int k : removed) {
			A.remove(Integer.valueOf(k));
		}
	}
}

문제

백준에서 '출력초과'가 났다.

원인

A의 원소부터 도니까, 예제1에같은 부분에서는 2의배수가 지워지지 않는다.
테라토스테네스의 체는 2부터 시작하며 도는것이다!
따라서 2부터 2배, 3배... 하며 해당 값을 삭제해야한다.

해결

for(int i : A) -> for(int i=2; i<=N; i++) 수정했다.

Troubleshooting 4

문제

백준에서 '시간초과'가 났다.

원인

1. 제곱근까지만 수행하면 되는데, N까지 수행했다.
2. 지울원소를 저장하는 배열을 따로 선언해서, 이 배열에 저장하고, 비교하면서 삭제하는 연산 수행에 시간이 많이 들었다.

해결

1. 제곱근까지만 검사를 수행했다.
2. 지울 원소를 저장하는 배열을 삭제하고, 그냥 기본 배열에서 소수가 아닌것은 0으로 바꿔주는 작업을 했다.
   -> 인덱스와 데이터값을 맞추어야하기때문에, 출력할때 M부터 N까지만 출력해야함
   -> 소수확인하는 작업은 2부터 N제곱근까지 수행!
   -> ArrayList대신 배열 사용(크기는 N+1)

제출코드

import java.util.Scanner;
import java.util.ArrayList;

public class Main {
static int N;
static int M;
static int[] A;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		M = sc.nextInt();
		N = sc.nextInt();
		A = new int[N+1];
		for(int i=2; i<=N; i++) {
			A[i] =i;
		}
	
		primeNumber();
		for(int i=M; i<=N; i++) {
			if(A[i] != 0) {
				System.out.println(A[i]);
			}
		}
	}
	public static void primeNumber() {
		for(int i=2; i<=Math.sqrt(N); i++) {
			if(A[i] ==0) {
				continue;
			}
			for(int j=2*i; j<=N; j= i+j) {
				A[j] =0;
			}
		}
	}
}

공부한 사항

• ArrayList의 원소 삭제
  remove(index i)
  remove(Object o) : ex) remove("d")

• ArrayList의 원소 변경
  set(int index, E element)

• 제곱근(루트)구하기 : Math.sqrt() -> import할 것 없음