* 어떤 수 C에 대해 소수인지 아닌지 판단하는 데 걸리는 시간: O(루트 C)
* 2 ~ (루트 C)까지만 확인하면 되기 때문
* 그렇다면 1 ~ 1,000,000까지의 모든 소수를 구하는 데 걸리는 시간?
* 총 N개의 수 * 각각 소수인지 판단하는 시간복잡도
* = N * O(루트N) = O(N루트N)
* 즉, 1,000,000 * 1,000 = 10억 = 10sec
* '에라토스테네스의 체'의 개념
1. 2부터 N까지의 모든 수를 적는다.
2. 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다.
3. 그 수를 지우고 소수로 저장한다.
4. 그 수의 배수를 지운다.
* 예를 들어, 1~100 까지의 수에서 모든 소수를 구해보자
* 2, 3, 5, 7의 순서로 위의 방법을 적용하면
* 11부터는 11*11 = 121(100초과)이기 때문에 더 이상 수행할 필요가 없다.
// '에라토스테네스의 체'를 이용한 start ~ end 범위의 수에서의 소수 구하기
Scanner s = new Scanner(System.in);
int start = s.nextInt();
int end = s.nextInt();
ArrayList<Integer> primeList = new ArrayList<>();
boolean[] checkPrime = new boolean[n + 1]; // true : 지워짐, false : 지워지지 않음
for (int i = 2; i <= end; i++) {
// 지워지지 않은 수는 소수
if (!checkPrime[i]) {
primeList.add(i); // 2~end 까지의 소수 저장
// i가 1,000,000 인 경우 i*i는 범위를 넘어가므로 j=i*i -> j=i*2
// for (int j = i * i; j <= n; j += i){
for (int j = i * 2; j <= end; j += i) {
checkPrime[j] = true; // 지워지지 않은 수의 배수들을 지운다
}
}
}* 소인수분해: 정수 N을 소수의 곱으로 분해하는 것
* 간단한 풀이법
* 소수를 구할 필요 없이
* 2~루트num 까지의 수를 순서대로 반복해서
* N를 나눌 수 없을 때까지 계속해서 나눈다.