1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

void euler(int n) {
    cnt = 0;
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) {
            pri[++cnt] = i;
        }
        for (int j = 1; j <= cnt; j++) {
            if (1ll * i * pri[j] > n) break;
            vis[i * pri[j]] = 1;
            if (i % pri[j] == 0) break;
        }
    }
}