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
as a cursor to go up and up every number possible.*currentPossiblePrime* - Check if
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*currentPossiblePrime*is then set to false.**isPrime** - Add the newly found prime number to the
list, and increase the primeCount value. This way, when primeCount exceeds the total amount of requested primes, the main loop exits.**primeNumbers**

**FIRST: GET THAT LIST OUTTA HERE.**

*list into an array. This adds some complications:*

**primeNumbers**- 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

**SECOND: MAKE THAT SECOND LOOP A BETTER PLACE**

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
instead of**primeNumbers[i]**(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.*possibleFactor*

- Now, the if statement uses another method to check if
can be divided by*currentPossiblePrime*(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 +*possibleFactor***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 thatdivides**primeNumbers[i]**! Modulo is goddamn useful in situations like this one.**currentPossiblePrime**

*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.

**RESULT**

*Addendum:*

*Addendum:*

*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.*

I have a better algorithm I did for a programming task, I’ll upload it if I can dig it up

There are some better ways of doing this. I guess you could improve it further by increasing the currentPossiblePrime by more than one. I just found a wiki page with a nice way of improving it further. http://en.wikibooks.org/wiki/Efficient_Prime_Number_Generating_Algorithms

I have a better sauce I made for a catering task, I’ll cook it if I can dig it up.

private void FindPrimes()

{

//There are no prime numbers pre 2

if(maxNo < 2)

{

MessageBox.Show("No Prime Numbers Found");

}

else

{

//2 is a prime number

//even numbers after 2 are not so do not check

listBox1.Items.Add(2);

double maxSqrt = Math.Sqrt(maxNo);

//Bit Array to keep track of removed numbers

BitArray removed = new BitArray(maxNo + 1);

//start looping at 3 and only check the odd numbers

//After finding a prime remove the numbers from its square and forward

//as ones previous should have already been done

for (int i = 3; i <= maxNo; i += 2)

{

if (!removed[i])

{

//stop before the square root of the max number

if (i < maxSqrt)

{

//stop before the max number

for (int j = i * i; j <= maxNo; j += 2 * i)

{

removed[j] = true;

}

}

listBox1.Items.Add(i);

}

}

}

Hello, talk about late to the party.

Anyways, this was a good example of optimization. (I also enjoyed the Pimp My Ride parody !).

However, for increasingly larger amounts of larger primes (see RSA : http://en.wikipedia.org/wiki/RSA_(algorithm)), a different approach is required.

One way to go about it is probabilistic algorithms; in this case, you would generate a random large odd number and then check if it’s a prime.

There are a number of tests available do to so; I have implemented the Miller-Rabin primality test in Java but don’t have the code available (make use of BigIntegers !).

Each test has a high probability of truthfulness : in Miller-Rabin’s case, it returns a false positive 1/4 of the time. To strengthen the result, the test can be run multiple times and the probability of a false positive would decrease by a factor of 1/4 each time.

Other tests include Fermat’s test and the Solovay-Strassen test (see http://en.wikipedia.org/wiki/Primality_test).

Note that there are special numbers called Carmichael numbers (see http://en.wikipedia.org/wiki/Carmichael_number) which the tests do not pick up on.

However, they are extremely rare and on average it is unlikely to cause problems (unless you’re in a mission critical project and you’re relying on prime numbers for some reason).