bbolker / bbolker/math1mp

HW 2 issues

Open
#4 1 comment 0 reactions 0 assignees View on GitHub
Dominant language
HTML
Stars
6
Forks
8
PR merge metrics
No merged PRs in 30d

Description

One potential problem with question 1 (Eratosthenes' sieve) which will lead to your program working correctly but slooooowly for large values of `n`) is doing *trial division*. In other
words, suppose your code contains a `for` loop like this:

```
for i in range(counter,n+1):
if i%counter == 0:
list[i] = False
```

It will go through *every value between counter and n+1* and test whether it
can be divided evenly by `counter` or not. That's very slow. The beauty
of Eratosthenes' sieve is that you don't have to do any division at all:
you know that `2*counter`, `3*counter`, `4*counter` ... are all non-prime.

You can do this without trial division (i.e., step through the non-prime values) either with a `for` loop (changing your starting point and using a different step) or with a `while` loop (starting a loop
counter `j` at `2*counter` and adding (`+=`) `counter every` time through the loop).

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.