Project Euler

Project Euler #23 : 두 초과수의 합으로 나타낼 수 없는 모든 양의 정수의 합은?

jyheo98 2020. 8. 7. 14:04
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
int main() {
    VI c;
    for (int i = 1; i <= 28123; i++) {
        int sum = 0;
        for (int j = 1; j < i; j++) {
            if (i % j == 0) sum += j;
        }
        if (sum > i) c.pb(i);
    }
    vector<bool> vis(28124);
    rep(i, 0, c.size()) {
        rep(j, 0, c.size()) {
            if (c[i] + c[j] <= 28123) {
                vis[c[i] + c[j]] = 1;
            }
        }
    }
    int sum = 0;
    for (int i = 28123; i >= 1; i--) {
        if (vis[i] == 0) {
            sum += i;
        }
    }
    cout << sum;
}
cs

20초 쯤 걸렸다. 어떡하지?!