in Books, Doing Books, How to Solve it by Computer

How to Solve it by Computer #6

Problem 2.7.1: Design an algorithm that counts the number of digits in an integer.

Again, not a super interesting problem but one which we can solve for free. And I love free stuff.

So is the next one.

Problem 2.7.2: Design an algorithm to sum the digits in an integer.

 

And this one is good too.

Problem 2.7.3: Design an algorithm that reads in a set of n single digits and converts them into a single decimal integer. For example, the algorithm should convert the set of 5 digits {2,7,4,9,3} to 27493.

 

And that’s why it’s cool to make small complete functions without side-effects. Reusability, baby.

Problem 3.4.2: It is possible to implement a sieving algorithm which crosses out each composite (non-prime) number exactly once rather than a number of times. […] Try to implement this algorithm aka. Sieve of Eratosthenes.

The wikipedia page got a cool animation of this algorithm. It’s a great starting point to start with this.

Let’s make this interactive. I start with a list of all integers from 2 to 40:

Now, imagine we know already that 2 is a prime number.

What we would now do is remove every number which is a multiple by 2. Or whose characteristic is mod 2 = 0.

 

Neat. Now we just need to find the next prime. We know that the next bigger number in our number list is a prime, in this case 3. And then we start again.

Let’s write a function:

I was surprised how small and easy to function is. Let’s go through it. We start easily with creating a list of numbers, like before. It starts with 2 and ends with n. Also we have an empty collection primes in which we put our primes. We know that the first element of our list numbers is always a prime, so we can put that into there. The next step is to remove all multiplies of that prime in our list. Now we just recursively call that function again. This runs so long until there’s no number left in numbers and the function returns our – now – big list of primes.

 

Neat.

Write a Comment

Comment