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…
Questa settimana il torero Israel Lancho è stato incornato durante una corrida. Sebbene le sue condizioni siano gravi, il torero non è in pericolo di vita. Quello che mi sconvolge è leggere sui giornali: “Questa settimana la corrida finisce tragicamente…”
Invece quando muore solo il toro, dopo un’agonia interminabile, con spade e lance piazzate nella schiena e nel collo, non finisce tragicamente?
Fossi stato io a dover scrivere l’articolo, l’avrei intitolato: “Anche questa settimana la corrida finisce tragicamente…”.
D’altronde, dice il saggio: chi è causa del suo mal pianga se stesso.
Io tifo sempre e solo per il toro.
Qosmio X300-122
Intel Core 2 Duo T9400 (2.53GHz, 6MB L2, 1066MHz FSB)
HD 400GB – RAM 4096MB DDR3 – Display Lcd 17″ wide TruBrite
Wi-Fi 802.11 a/g/n – Sistema operativo Windows Vista Ita Home Premium
Gigabit Ethernet – Bluetooth – USB/eSATA – S/PDIF – Subwoofer
Webcam 1.3Mpixel con microfono integrati – HDMI-CEC fino a 1080p
Scheda video NVIDIA GeForce 9800M GTX 1024MB dedicata GDDR3
Causa inutilizzo vendo questo portatile.
E’ esattamente come nuovo e in perfette condizioni.
In regalo una borsa nera, con tracolla, della Oliepops.
Prezzo: 1100 euro + iva (1320 euro ivato)
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.
