This notebook was prepared by [Thunder Shiviah](https://github.com/ThunderShiviah). Source and license info is on [GitHub](https://github.com/ThunderShiviah/code_guild).

Challenge Notebook

Problem: Implement list_primes(n), which returns a list of primes up to n (inclusive).

Constraints
Test Cases
Algorithm
Code
Unit Test
Solution Notebook

Constraints

Does list_primes do anything else?
- No

Test Cases

list_primes(1) -> [] # 1 is not prime.
list_primes(2) -> [2]
list_primes(12) -> [2, 3, 5, 7 , 11]

Algorithm

Primes are numbers which are only divisible by 1 and themselves.

5 is a prime since it can only be divided by itself and 1. 9 is not a prime since it can be divided by 3 (3*3 = 9). 1 is not a prime for reasons that only mathematicians care about.

To check if a number is prime, we can implement a basic algorithm, namely: check if a given number can be divided by any numbers smaller than the given number (note: you really only need to test numbers up to the square root of a given number, but it doesn't really matter for this assignment).

Code



In [29]:

    
def list_primes(n):
    lst = []
    for num in range(2, n + 1):
        for number in range(2, num):
            if num % number == 0:
                break
        else:
            lst.append(num)


    return lst
list_primes(100000)

Unit Test

The following unit test is expected to fail until you solve the challenge.



In [3]:

    
# %load test_list_primes.py
from nose.tools import assert_equal


class Test_list_primes(object):

    def test_list_primes(self):
        assert_equal(list_primes(1), [])
        assert_equal(list_primes(2), [2])
        assert_equal(list_primes(7), [2, 3, 5, 7])
        assert_equal(list_primes(9), list_primes(7))
        print('Success: test_list_primes')


def main():
    test = Test_list_primes()
    test.test_list_primes()


if __name__ == '__main__':
    main()









    



---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
<ipython-input-3-daa21d192bd5> in <module>()
     19 
     20 if __name__ == '__main__':
---> 21     main()

<ipython-input-3-daa21d192bd5> in main()
     15 def main():
     16     test = Test_list_primes()
---> 17     test.test_list_primes()
     18 
     19 

<ipython-input-3-daa21d192bd5> in test_list_primes(self)
      6 
      7     def test_list_primes(self):
----> 8         assert_equal(list_primes(1), [])
      9         assert_equal(list_primes(2), [2])
     10         assert_equal(list_primes(7), [2, 3, 5, 7])

/home/thunder/anaconda3/lib/python3.5/unittest/case.py in assertEqual(self, first, second, msg)
    815         """
    816         assertion_func = self._getAssertEqualityFunc(first, second)
--> 817         assertion_func(first, second, msg=msg)
    818 
    819     def assertNotEqual(self, first, second, msg=None):

/home/thunder/anaconda3/lib/python3.5/unittest/case.py in _baseAssertEqual(self, first, second, msg)
    808             standardMsg = '%s != %s' % _common_shorten_repr(first, second)
    809             msg = self._formatMessage(msg, standardMsg)
--> 810             raise self.failureException(msg)
    811 
    812     def assertEqual(self, first, second, msg=None):

AssertionError: None != []

Solution Notebook

Review the Solution Notebook for a discussion on algorithms and code solutions.



In [ ]: