Home > Prime numbers > Prime numbers

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);
}
Advertisements
Categories: Prime numbers Tags: ,
  1. September 20, 2011 at 11:41 am

    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.

    • jfdube
      September 20, 2011 at 12:19 pm

      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.

  2. sylvain
    October 4, 2014 at 9:29 pm

    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.

  3. steelhg
    October 6, 2014 at 6:25 am

    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….)

    • jfdube
      October 11, 2014 at 11:14 am

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

  1. September 27, 2011 at 12:14 pm

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: