P6588

[baekjoon-6588] 골드바흐의 추측

시간 초과

Baekjoon-1978 소수 찾기 에서와 같은 로직으로 소수 배열을 만들었을 때, 그 범위가 1000000 이러니까 아예 출력조차 안 되는 것. 그래서 로직을 바꿔 돌렸더니 시간 초과 문제 해결 !!

원래의 시도

boolean[] nums = new boolean[1000001];

nums[1] = true;
for (int i = 2; i <= 1000000; i++) {
    for (int j = i+1; j <= 1000000; j++) {
        if (j % i == 0) nums[j] = true;
    }
}

이번의 시도

원래는 하나씩 돌면서 나눗셈 해봤는데, 이 로직은 그 숫자의 배수들만 찾아서 들어가는 느낌 !!

boolean[] nums = new boolean[1000001];

nums[1] = true;
for (int i = 2; i <= 1000000; i++) {
    for (int j = 2; i*j <= 1000000; j++) {
        nums[i*j] = true;
    }
}