Yo dawgs. Today me and my homies laid our eyes on some sweet piece of code, that finds a list of prime numbers. The man’s name is P.J, and he’s asked us to pimp his code. Let’s move to his crib and meet the guy.
This is the part where I knock on the person’s door and he pretends he’s surprised to see me.
So, P.J wants his code to run faster and to look cooler. That seems like a job for my crew. Show me the damn stuff, man.
As you can see, dat shit makes a list of prime numbers. But P.J forgot to include the primeNumbers list declaration in that snippet. Come on boy, you can do better than that. Now take a good look at this, man. Can you see what the three steps are?
- Use currentPossiblePrime as a cursor to go up and up every number possible.
- Check if currentPossiblePrime can be divided by a factor. Check out the second while loop, and you can see that the factor is increased until it’s half the value of the currentPossiblePrime, because the number cannot be divided by anything below 2 that isn’t 1. That means the currentPossiblePrime is prime. currentPossiblePrime is suspected to be prime until it is proven otherwise: when it can be divided by a factor, the loop exits, as isPrime is then set to false.
- Add the newly found prime number to the primeNumbers list, and increase the primeCount value. This way, when primeCount exceeds the total amount of requested primes, the main loop exits.
FIRST: GET THAT LIST OUTTA HERE.
- Each time the function is called, the array must be recreated with a new statement. We can’t just remove everything that’s in it, because the request might be for a different amount, so we have to create a new one. We’re not in C++, so we don’t give a f**k about calling delete.
- Instead of an Add statement, set the current prime number to the newly found prime number
The while loop is all cool, but can be more efficient. You ain’t seen nothing until you witness the power of the modulo.
- First off, check out that for loop. We’re looping through the prime numbers. Why the f**k would you want to do that? Well man, when testing for a prime number, there is no need to check if all numbers before it can divide it. Nope. You just need to check if you can divide it by any prime number that comes before it! Picture that in your headbox: you want to check if 13 is prime. You start by checking if you can divide it by 2, and surprise, you can’t. Why, then, would you check if 4 (2 * 2) or 6 (2 * 3) divide 13, since they’re all multiples of 2.
- The second stop condition of the ‘for’ loop is the same as on the previous code, but with primeNumbers[i] instead of possibleFactor (because we got rid of teh motherf***er). Small change is that the /2 is now a *0.5f. Multiplying is more efficient than dividing, so if you want to nitpick go for it when you feel like it.
- Now, the if statement uses another method to check if currentPossiblePrime can be divided by possibleFactor (now ditched for primeNumbers[i], since we’re using the prime numbers themselves to test for divisibility). See that %? This is modulo. It returns the rest of an integral division. This means 13 % 2 would yield 1, as 13 = 2 * 6 + 1. See where I’m heading there? If the modulo of a division is 0, it means the division yields no rest! So, currentPossiblePrime % primeNumbers[i] = 0 means that primeNumbers[i] divides currentPossiblePrime! Modulo is goddamn useful in situations like this one.
- Note: Instead of adding a !isPrime condition in the for loop, it is also possible to add a break when isPrime is set to false. It is more efficient, as only called once, but adds lines, and in Pimp My Algorithm, we don’t want no added lines.
THIRD: FIX THE REST
Now all this messing around has got us into some trouble. What trouble? Running the algorithm will give you a damn “Divided by zero” exception at the for loop. How the f**k do you get out of this shit? Well, initialise the first prime number to 2. In the for loop, the first comparison will check the array of prime numbers. Problem is, it’s empty. Filled with nada. Which is why you need to set the first prime number yourself. You can set the currentPossiblePrime to the same number, as it will be increased by one on its first time through the loop.
Today’s networking labs were about multithreading in distributed applications. What I love about Peter Robinson’s labs is that there is always something to sidetrack on. A ‘sidequest’ of sorts.
Though they would usually be pig latin related, today’s sidequest is an algorithm set to find a list of X prime numbers. The basic algorithm was pure brute force, as it was written for demonstation purposes to show how a slow application can freeze an interface if not running on a separate thread.