A review of the basics... but mainly riddles!

In our opinion, the best way to learn a coding language is to just start using it and figure out things as you go along. It may sound a bit odd to approach something as systematic as computer programming in such a random way, but don't worry: it works out just fine.

When you need to look up some new syntax or get help with how Python can be used to solve a certain problem, where should you go? The Python Tutorial. With a basic understanding of sections 3, 4, and 5 you can go a very long way! They cover:

- An introduction to how Python handles numbers, strings, and lists;
- Control flow (executing code based on some condition, looping over pieces of code, functions);
- Built-in data structures and operations (lists, sets, tuples, dicts).

We won't repeat any of that stuff here; you should refer to those pages as needed while we tackle the tasks below.

To get started, let's try the first problem on Project Euler. If you want to be able to check your answer and track your progress, you will have to register for a free account.

Here is our solution:

```
# Problem 1
sum = 0
for i in range(1,1000):
if i%3 == 0 or i%5 == 0:
sum += i
print(sum)
```

There are a few key ideas to take note of:

- Variable assignment. In Python, you just use the = sign, no need to declare the
*type*of variable. - The
*for*loop. Notice the compact notation: no extra brackets as in many other languages. The range function simply returns integers between 1 and 999, inclusively. - The
*if*statement. Again, no extra brackets are needed. The == sign is used to evaluate*equality*. - The print() statement outputs to the terminal.

**Perhaps the most important thing to notice is that scope is defined by indentation: everything that belongs to the for loop is indented once with respect to the line that it started on. The same is true for the if statement.**

Now it is your turn to try one.

Success?

Ok, let's do one more. Project Euler Problem 3 is asking us to find the largest prime factor for a very large number. We are not going to be fancy here: brute force is fine. But, we should start thinking about *coding style*. Checking for a prime number is a common enough task and we should write a *function* for that job.

Now let's try something with more of a Python focus. Nadav Samet launched the Python Challenge back in 2005 as "an entertaining way to explore the Python Programming Language." It is essentially a series of riddles, each of which requires a little bit of Python to solve. The game is very addictive. I am currently on Level 6 of 33 and spend far too much time working on it.

Nice work today!

A last thought on Project Euler Problem 3 (spoiler alert: solution below). One person at the meet-up today had an *excellent* solution for this problem... I don't remember exactly how he did it, but I've tried to reproduce something similar here.

Recall that we want to find the largest prime factor for a very large number. The key idea here is the fundamental theorem of arithmetic, which states that any number is either prime or can be produced by multiplying a unique set of primes together. Let $X$ represent the number we wish to factor and $p$ a prime number. If $X$ is not prime it can be expressed as:

\[ X = p_1\times p_2\times p_3 \times ... \times p_n \]So our search for the largest prime factor is really a search for $p_n$ and we can rearrange the above equation to solve for it

\[ p_n = \frac{X}{p_1\times p_2\times p_3 \times ... \times p_{n-1}} \]Our code doesn't have to check every number from 1 to $X$. We just have to search for prime numbers. Whenever we find one that is a factor of $X$ we divide $X$ by it (we should actually try to divide $X$ by the factor many times as prime factors can be repeated). We stop when our search passes the current value of $X$.

```
number = 600851475143
prime_list = [2]
largest_prime_factor = 1
i = 3
while i <= number:
for j in prime_list:
if i%j == 0:
break # not prime so move on to next number
else:
prime_list.append(i) # we made it through without breaking, number must be prime so append it to the list
if number%i == 0:
largest_prime_factor = i
number = int(number / i)
i += 1
print(largest_prime_factor)
```

This code introduces some new ideas. First, prime_list is a *list* (like an array in other languages) and we can access values stored in the list using [], *i.e.* prime_list[0] stores the value 2. We also introduce *break,* which simply tells Python to leave the current loop. The *else* is special: it only runs IF the for loop gets all the way to the end (*i.e.* the break statement is never encountered). This is some pretty dense Python!