<jupyter_start><jupyter_text>Discussion 5: Prime Numbers Group Members and Roles- Group Member 1 (Role)- Group Member 2 (Role)- Group Member 3 (Role) IntroductionIn this Discussion activity, our focus will be on writing some efficient Python functions for checking whether numbers are prime.   §1. Test PrimesFirst, write a function called `is_prime(n)` that tests whether a integer `n` is prime. Do so by checking whether `i` divides `n` for every positive integer `i < n`. Remember that `0` and `1` are not prime. You should return `True` if the input is prime, and `False` otherwise. **Note:** `i` divides `n` iff `n % i == 0`.Check that your function works by checking `9973` (prime) and `9977` (not prime).<jupyter_code># write is_prime(n) here<jupyter_output><empty_output><jupyter_text>§2. Test PrimesYou may remember from math class that it's not necessary to check *all* numbers `i < n` to tell whether `n` is prime. In fact, it suffices to check only numbers `i` such that $i \leq \sqrt{n}$ (why?). Write a new function called `fast_is_prime(n)` that takes advantage of this fact. Check your function using the same tests as above. ***Hint***: ```pythonimport mathmath.sqrt(2)```<jupyter_code># write fast_is_prime(n) here<jupyter_output><empty_output><jupyter_text>§3. Compare SpeedJupyter comes with a special "magic macro" that lets you compare the execution speed of your functions. To use it, add `%timeit` ("time it") in front of your function call. Write and run the following two lines: ```python%timeit is_prime(9973)%timeit fast_is_prime(9973)```You'll see some summary statistics based on a large number of repetitions of your function. How much faster is `fast_is_prime` than `is_prime`?<jupyter_code># try testing 9973<jupyter_output><empty_output><jupyter_text>Now test `n = 1000003`. How much faster is your implementation of `fast_is_prime()`? **Note:** What is $\sqrt{1,000,000}$?<jupyter_code># try testing 1000003<jupyter_output><empty_output><jupyter_text>§4. All Primes Up to `n`Suppose I want to find all primes up to `n`, returned as a list. First, write a **very short** function which does this using `fast_is_prime()` from above. How short can you make this function definition? Can you get it into a single line using (conditional) list comprehensions and `lambda` notation? Test your function by returning all primes up to 20. **Note**: `1` is not a prime number.<jupyter_code># write primes_up_to(n) here<jupyter_output><empty_output><jupyter_text>§5. Another ApproachSo far, we are testing whether each individual number is prime. This is inefficient. In fact, a number `n` is prime if and only if it is not divisible by any *prime number* `p` such that `p < n`. In other words, we could make our function even faster if we used knowledge of previous primes when checking the next one. Write a function called `primes_up_to_2(n)` which uses this idea. Here's the pseudocode: 1. Create and update a list of known primes, which starts off empty. 2. For each `k < n`, check whether `k` is divisible by any primes on the list. If not, add `k` to the list. 3. Finally, return the list. **Note**: This code may be a little slower than your previous function -- that's ok! We'll speed it up in a bit. **Hint**: in this and the following part, if you find it helpful, you may initialize the list of primes with value `primes = [2,3]`. `1` is not prime!<jupyter_code># write primes_up_to_2(n) here<jupyter_output><empty_output><jupyter_text>Now use `%timeit` to compare the speed of your two implementations, and comment on the result.  Check the time for both small and large numbers of `n`.<jupyter_code># timing tests here<jupyter_output><empty_output><jupyter_text>---If you've made it this far, **great job**! If there are more than 5 minutes left in Discussion, go ahead and continue on to the remaining part, in which you'll create an even faster `primes_up_to` function. Otherwise, feel free to submit your worksheet. Finding some time to work with your group to complete the worksheet is optional but heartily recommended. ---  §6. Ludicrous Speed    When we implemented `primes_up_to_2(n)`, we used one useful piece of information, but we "forgot" about the $\sqrt{n}$ thing. More specifically, it's sufficient to check whether `n` is divisible by any prime *less than or equal to* $\sqrt{n}$ . Write a new function called `fast_primes_up_to(n)` which uses this idea. You can do this by making modifications to `primes_up_to_2(n)` from the previous part.<jupyter_code># write fast_primes_up_to(n) here<jupyter_output><empty_output><jupyter_text>Use `%timeit` one more time to compare your three implementations, and comment on the result.<jupyter_code># timing tests here<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.09215520877266976, 'fraction_numerical': 0.014550822437789962, 'mean_word_length': 5.282119205298013, 'pattern_counts': {'":': 0, '<': 41, '<?xml version=': 0, '>': 37, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '9', 'dir': 'jupyter-structured-clean-dedup', 'id': '95754', 'license': 'MIT', 'n_tokens_mistral': 1457, 'n_tokens_neox': 1380, 'n_words': 671, 'path': 'discussion/primes.ipynb', 'repo_name': 'mm5110/PIC16A', 'size': '4742'}