## Prime numbers

Prime numbers are a very interesting topic. I often find myself quite uncomfortable when setting my car’s radio volume on an even number, and I really feel better when it’s a prime number. But this is a complete different story.

So, what are the uses of prime numbers in programming? Cryptography, random numbers generation, better hashing functions, etc. One thing that I recently discovered about prime numbers is that if you multiply *n* different primes together, it creates a special composite number (if anyone knows the real name of those, please tell me) that has a quite interesting property: there’s a way to know if a certain prime *p* was used or not to compose it simply by dividing by *p*. If the result is an integer, then *p* was used to compose the number. Take this example:

- 3 * 7 * 13 * 53 * 227 = 3284463

To know if prime number 19 was used to compose it, we do:

- 3284463 / 19 = 172866.474

Since the result is not an integer, 19 wasn’t used to compose the number 3284463. But, if we take a look at:

- 3284463 / 3 = 1094821

3284463 / 7 = 469209

3284463 / 13 = 252651

3284463 / 53 = 61971

3284463 / 227 = 14469

A practical usage of this property is for a RTTI system. By assigning a different prime number to each class in the hierarchy, and by multiplying each child’s class value by it’s parent value, we can determine if a class *A* derives from class *B* simply by dividing its composite number by *B*‘s number, instead of going through all the parents chain:

Bool Class::IsChildOf(const Class* B) const { return ((Prime % B->Prime) == 0); }

That’s a clever idea with the RTTI system. Sounds like arithmetic compression for bitfields! Though I guess you’d need more than 32-bit integer precision if you intended to support more than 4 – 5 levels of hierarchy.

I have approximately 85 classes in my home project, with a maximum depth of 7. I use 64-bits, but most probably that 128 would be required for bigger projects. I’ll try to implement this at work to see if it’s feasible or not. Also, attributing smaller numbers on top of the hierarchy seems a good idea.

The example you gave is awesome because, as you pointed out, it is a very interesting property that dividing X by p will tell you if prime number p was used. But when I showed this to my wife (a grade-school teacher) she said: Well that’s obvious and any 10yo could tell you that. Remember when we learned about factorization? Basically, if you factorize 3284463, you will get 3 * 7 * 13 * 53 * 227. Then you see that 19 is not used. That is awesome, because it all makes sense when you think about the definition of factorization.

Why not just use a power of 2 for each class and OR them all together? and to find the if D inherits from B, just AND their numbers together. So basically using a bit field. Operations will be easier to perform and the hierarchy can grow bigger (2*2*2*…. VS 2*3*5*7….)

That would work, too. This is basically different ways of encoding the same source information, In practice, both solutions wont work when the class hierarchy is big and deep. It was just a cool fact. that`s all. 🙂