fizzbuzz icon indicating copy to clipboard operation
fizzbuzz copied to clipboard

Error in Chapter 4. Euclid's Solution example

Open vlad-bezden opened this issue 4 years ago • 0 comments

In chapter 4 (Euclid's Solution) example:

def primes_up_to(n: int) -> List[int]:
    #             0      1         2,      ..., n
    candidates = [False, False] + [True] * (n - 1)
    for p in range(2, int(math.sqrt(n))):
        # if we haven't already eliminated p as a prime
        if candidates[p]:
            # eliminate all multiples of p, starting at p ** 2
            for m in range(p * p, n + 1, p):
                candidates[m] = False
    # return the indices that weren't eliminated
    return [n for n, prime in enumerate(candidates) if prime]

it should be:

    for p in range(2, int(math.sqrt(n) + 1)):

Without +1 it will output 961, which is not prime (31* 31)

vlad-bezden avatar Aug 21 '20 20:08 vlad-bezden