Non so, forse perchè al giorno d’oggi si tende a dare fiducia agli strumenti tecnologici, tipo i traduttori automatici, o forse perchè la qualità degli insegnamenti nelle università italiane è diminuita drasticamente, o forse solo per la spropositata tirchieria del capo progetto, sta di fatto che ho sbagliato a inserire il captcha nel form che mi permette di ricevere la mia agognata copia di windows 7 per il portatile. Bene… dal regno dei traduttori estinti della mentor media, questo è stato il risultato:
Le lacrime…
As you may or may not know, Telltale Games has launched the new episode of Monkey Island. Divided in five chapters, or “tales”, the game is going to be released “tale after tale”. The first one is already available, and the second one is coming out today. So, being a huge fan of m.i. and having completed all the previous games, I really couldn’t help buying this one too. I won’t say much about the first chapter, except that is funny and really nice. The only thing I don’t like that much is the 3D moving system mouse controlled, which is still to be improved imho.
Anyway, this post isn’t really about the game so, let’s get to the point:
Whatever you decide to do about the game, please take two minutes of your time and watch the “I wonder what happens” mini movies you can find here.
They are just too funny.
The Euler Totient Function (a.k.a. phi function) gives the number of positive integers that are smaller than a given positive integer n and coprime to it.
I was reading the wikipedia page about it and found out that the python implementation that is linked at the end of the page runs in O(n). That is sure not a good result, since when n is a big number (say ten billions) the function does approximately n operations within a for cycle.
Now, if you factor n into primes, you can apply this formula:
phi(n) = (P1-1)*P1^(e1-1) * … * (Pk – 1)*Pk^(ek-1)
where n = P1^e1 * … * Pk^ek
So, a very good way to implement the phi function would be:
- Calculate an array of primes p, being sure that the last prime in the array is greater than the square root of n
- Factorize n into primes
- Apply the formula given above and return the result
Read more…
Being a passionate challenge site player, it happens that I need to generate a list of all the prime numbers that are less than a certain bound. It is very useful to have a fast method to do that, expecially when you need the list to solve a challenge. The faster the generation is, the faster you solve the challenge and, more important, the faster you debug your solution until it is correct.
So, my first attempt was the simple trial division method: you start by putting 2 into a list and then check every odd number from 3 up to where you want to get and see if any of the primes you have already found (you just check from 2 upto sqrt(n)) divides your candidate number n. If you find a prime divisor, then n is composite, otherwise it is prime. If it is prime you add it to the list, get the next odd number n and start again.
This method has one advantage: you just work in-place, so you don’t waste any additional memory while you are generating the list. The downside, though, is that trial division is not that fast. Read more…
Finally!
Moving day is over, welcome to the new zerovolt.com.