@rkenmi - Primes

# Primes

### Primes

##### Updated on October 5, 2017

Let's discuss primes!

A natural number is considered a prime if it is:

• Greater than 1
• Its divisors are only 1 and itself

Examples:

$$5$$ has two divisors: $$\frac{5}{1} = 5$$ and $$\frac{5}{5} = 1$$

Which means $$5$$ is a prime.

$$4$$ has three divisors: $$\frac{4}{1} = 4$$ and $$\frac{4}{4} = 1$$ and $$\frac{4}{2} = 2$$

Which means $$4$$ is not a prime.

### Problem

Given an integer $$n$$, write a function that returns a list of all prime numbers up to $$n$$ (inclusive).

### Input

• $$n$$: Integer

### Examples

prime_func(5) => [2, 3, 5]
prime_func(10) => [2, 3, 5, 7]
prime_func(0) => []


### Strategy

A quick, brute-force way to solve this is to go through all numbers from $$2$$ to $$n$$ and evaluate each number if it is a prime.

We know that a number is prime if it only has 2 divisors. This means that if we run into more than 2 divisors, we can immediately say that this number is not a prime.

In order for us to evaluate each number (call it $$i$$) from $$2$$ to $$n$$, we'll need to check from $$2$$ to $$i$$.

def naive_primes(n):
primes = []
for i in range(2, n+1):
is_prime = True

for j in range(2, i):
if i % j == 0:
is_prime = False
break

if is_prime:
primes.append(i)

return primes


By default, we'll set the prime flag to true at the start of each iteration. The modulo operation i % j == 0 tells us that if this evaluation is true, then we have an additional divisor, implying that the number $$i$$ is not prime. As soon as we know that this number isn't prime, there is no need to iterate through the rest of the numbers; we'll set the prime flag to false and break from this inner loop to save some performance.

Lastly, we only add the number $$i$$ if and only if our prime flag is set to true.

This algorithm costs us $$O(n)$$ in space complexity for all prime numbers $$<=n$$ and quadratic time complexity.

### Improved Solution

We can actually do better by realizing that prime numbers have patterns that we can take advantage of.

Consider the prime number $$2$$.

We notice that all even numbers, i.e. $$4, 8, 32, 48, 102, ...$$ are not prime because it is divisible by the prime number $$2$$.

So, whenever we evaluate a number as prime, what if we use that number to somehow mark the future numbers as not prime?

We can implement this by having a boolean array flag, which will cost us a bit more in space complexity, but save us a good deal of performance in time complexity.

def primes(n):
primes = []

is_prime = [False, False] + [True] * (n-1)

for i in range(2, n+1):
if not is_prime[i]:
continue

primes.append(i)

for j in range(i, len(is_prime), i):
is_prime[j] = False

return primes


Since we want our is_prime boolean array to be aligned with $$0...n$$, we'll have the first two elements be False (since $$0$$ and $$1$$ are not prime by definition) and set the rest of the elements to be True (temporary default value).

We do a check at the start of each number evaluation by checking against the boolean flag in if not is_prime[i]: continue. If the number isn't a prime, we skip to the next iteration.

When we start at i = 2, the boolean flag is mostly full of True values, so the is_prime check doesn't do much for us initially. However, we will soon come to realize that it becomes very useful in a short amount of time.

Once we add $$2$$ to our primes list, we will clear the True flags for all numbers up to $$n$$ that are divisible by $$2$$. This essentially sets all the even numbers in the example above ($$4, 8, 32, 48, 102, ...$$) to the not prime flag.

Looking back now, since we completely skip numbers that correspond to False in the is_prime boolean array, as soon as we iterate to i = 3, we'll be saving a lot of performance due to skipping a lot of numbers. This effect of skipping number lowers as $$i$$ gets higher and higher, but all in all, this algorithm is much more efficient than our brute-force approach.