https://lucashsu95.github.io/LucasHsu.dev/python/112全國技藝競賽筆記/15-其他/spf

https://codeforces.com/blog/entry/54090

std::vector <int> prime;
bool is_composite[MAXN];

void sieve (int n) {
	std::fill (is_composite, is_composite + n, false);
	for (int i = 2; i < n; ++i) {
		if (!is_composite[i]) prime.push_back (i);
		for (int j = 0; j < prime.size () && i * prime[j] < n; ++j) {
			is_composite[i * prime[j]] = true;
			if (i % prime[j] == 0) break;
		}
	}
}

def sieve_spf(n):
    spf = [0]*(n+1)
    primes = []
    for i in range(2, n+1):
        if spf[i]==0:
            spf[i]=i
            primes.append(i)
        for p in primes:
            if p>spf[i] or p*i>n: break
            spf[p*i]=p
    return spf

|

v