12 能被 2 和 3 划掉，怎样让每个合数只被处理一次？

"""Every composite has exactly one owner: its smallest prime times the rest."""
from math import isqrt, prod


def require(ok, message):
    if not ok:
        raise AssertionError(message)


def linear_sieve(limit, mode="correct", emit=None):
    if type(limit) is not int or not 0 <= limit <= 100000:
        raise ValueError("integer 0<=limit<=100000 required; bool excluded")
    if mode not in ("correct", "no_break", "early_break"):
        raise ValueError("unknown teaching mode")
    least = [0] * (limit+1)
    marked = [0] * (limit+1)
    primes = []
    for i in range(2,limit+1):
        if least[i] == 0:
            least[i] = i
            primes.append(i)
            if emit:
                emit("prime", i, i, i, False)
        for p in primes:
            q = i*p
            if q > limit:
                break
            divides = i % p == 0
            if mode == "early_break" and divides:
                if emit:
                    emit("skipped", i, p, q, True)
                break
            least[q] = p
            marked[q] += 1
            if emit:
                emit("mark", i, p, q, mode == "correct" and divides)
            if mode == "correct" and divides:
                break
    return primes, least, marked


def trial_least(value):
    for divisor in range(2,isqrt(value)+1):
        if value % divisor == 0:
            return divisor
    return value


def factor(value, least):
    if type(value) is not int or not 1 <= value < len(least):
        raise ValueError("value must be in 1..limit")
    result = []
    while value > 1:
        p = least[value]
        if p < 2 or value % p:
            raise ValueError("invalid least-prime table")
        result.append(p)
        value //= p
    return result


def main():
    primes, least, marked = linear_sieve(30)
    print(f"primes_to_30={primes}")
    print(f"least[12]={least[12]}; factors[12]={factor(12,least)}; mark_count[12]={marked[12]}")
    print(f"composite_marks={sum(marked)}; composite_count={29-len(primes)}")
    redundant = linear_sieve(30,"no_break")
    premature = linear_sieve(30,"early_break")
    require(redundant[0] == primes and redundant[2][12] == 2, "remove-break counterexample")
    require(4 in premature[0], "early-break counterexample")
    print(f"without_break: primes_same={redundant[0]==primes}; marks[12]={redundant[2][12]}; total_marks={sum(redundant[2])}")
    print(f"break_before_mark: wrongly_lists_4_as_prime={4 in premature[0]}")
    limits = comparisons = 0
    for limit in list(range(301)) + [1000,10000]:
        primes, least, marked = linear_sieve(limit)
        expected = [x for x in range(2,limit+1) if trial_least(x)==x]
        require(primes == expected, "trial division prime list")
        for x in range(2,limit+1):
            want = trial_least(x)
            require(least[x] == want, "smallest divisor")
            require(marked[x] == int(want != x), "each composite exactly once")
            factors = factor(x,least)
            require(prod(factors) == x and all(trial_least(p)==p for p in factors), "factorization")
            comparisons += 1
        if limit >= 1:
            require(factor(1,least) == [], "one has no prime factors")
        limits += 1
    for invalid in (-1, True, 3.5, "30",100001):
        try:
            linear_sieve(invalid)
        except ValueError:
            pass
        else:
            raise AssertionError("invalid input accepted")
    print(f"limits_checked={limits}; number_checks={comparisons}; invalid_inputs=5")
    print("PASS: trial divisors, prime lists, unique marks and factor products agree")


if __name__ == "__main__":
    main()