잘못 구현한 에라토스테네스의 체(15897)

axiom·2021년 9월 12일
0

잘못 구현한 에라토스테네스의 체

1. 힌트

1) 주어진 코드를 곧이곧대로 구현하면 O(N2)O(N^2)의 시간 복잡도입니다.

2) 안쪽에 있는 for문을 n1n - 1이하의 ii의 배수의 개수 +1+ 1로 이해할 수 있습니다.

3) nn이하의 ii의 배수의 개수는 ni\lfloor\displaystyle\frac{n}{i}\rfloor로 나타낼 수 있고, 이 값은 O(n)O(\sqrt{n})종류의 값을 가집니다. 이를 O(n)O(\sqrt{n})시간에 반복하는 효율적인 방법이 존재합니다.

ahgus89님의 글 참조

2. 접근

1) 내가 문제를 푸는 과정을 수식화할 수 있을까?

안쪽 반복문의 jj를 나열하면 이와 같습니다.

1, 1+i, 1+2i, 1+3i...1,\ 1+i,\ 1+2i,\ 1+3i...

jj는 계속 증가하다가 최대 nn까지 늘어날 것입니다. 수열의 모든 수에 11을빼주면 이와 같습니다.

0, i, 2i, 3i...0,\ i,\ 2i,\ 3i...

맨 앞에 있는 00만 빼고 생각하면 이 수열의 원소의 개수는 nn이하의 ii의 배수의 개수입니다. 이를 ni\lfloor\displaystyle\frac{n}{i}\rfloor로 나타낼 수 있습니다.

2) 조화수열의 성질

ai=nia_i = \lfloor\displaystyle\frac{n}{i}\rfloor이라고 정의해서 수열을 써볼 수 있습니다. 곧이 곧대로 11부터 nn까지 반복하기엔 범위가 너무 큽니다. 우리는 aia_i의 값이 O(n)O(\sqrt{n})개의 서로 다른 종류만 가진다는 것에서 O(n)O(\sqrt{n})의 반복하는 방법이 있지 않을까 생각해 볼 수 있습니다. 자세한 설명은

ahgus89님의 글 참조

3. 구현

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int K = N - 1;
		long sum = N;
		int j = 0;
		for (int i = 1; i <= K; i = j + 1) {
			j = K / (K / i);
			sum += (long)(K / i) * (j - i + 1);
		}
		System.out.println(sum);
	}

}

1) 시간 복잡도

반복문 하나이지만, O(n)O(\sqrt{n})개의 값에 대해서만 반복합니다.

profile
반갑습니다, 소통해요

0개의 댓글