Submitted by matt_eaton
on Sun, 02/19/2017 - 03:18 AM
I was recently asked in a computational project to generate prime numbers to be used in public key hashing routines. The idea was that I needed to write an algorithm that finds prime numbers between a specific range and then those prime numbers would be randomly assigned to a list and then multiplied together in sequence to produce large complex numbers that would then, in turn, be concatenated together to form variations of public keys. Sounds mildly complex, right; but from an algorithmic standpoint the really only ask for me was to iterate through a list of integers between an upper and lower bound and check whether the current iterator is divisible by another value other than 1 - given a predefined function. One thing that struck me as odd though as I was designing the algorithm was how expensive the current function that I was asked to use was. The current routine was functional and did properly detect prime numbers, but the time complexity involved with the implementation was expensive and could potentially cause a resource issues as numbers grew larger and larger.. Below is a sample of the implementation I was asked to use:
def is_prime(num): i = 0 for e in range(1, (num + 1)): if num % e == 0: i += 1 if i > 2: return False return True
One thing that you may have noticed right away is that every iterator in the range between a lower and upper bound is iterated through from 1 to the lower bound to make sure the iterator is only divisible by 1. So, for example, if the lower bound was 500 then to check if a number was prime, at least 500 comparison's had to be made in order to at least even get to the lower bound. I thought to myself that there had to be a way to improve this because 500 is a relatively small lower bound to begin with and this is only going to get larger and larger.
As I was designing the algorithm I thought I would use the numbers 1 - 10 as a way to model this entire procedure. I landed on 10 because every number after 10 is based upon the numbers 1 - 10 anyways and if I simply was able to derive a multiple while looping from 1 to 10 then almost everything afterwards would also follow suite. This would then greatly reduce the time complexity of deriving prime numbers from large values too.
Below is a basic implementation that I came up with to weed out prime numbers and add them to a list. This implementation could be expanded upon probably, but for now this is still uses a brute force methodology.
primes = [] for i in range(lower, upper): # Add some common filters to reduce time complexity if i > 2 and i % 2 == 0: continue if i > 3 and i % 3 == 0: continue if i > 5 and i % 5 == 0: continue if i > 7 and i % 7 == 0: continue if i % 9 == 0: continue # If we have made is it this far, by the laws of multiples # we know that we do not have to go through the expensive # routine of checking if the number is prime or not # As the iterator grows the time complexity of checking if the number # is prime or not grows with it. primes.append(i)
I created a very simple sample of the source code from this project on my Github page here. Please check it out and let me know if you like it, or see something that could be improved upon. As always, let me know if you have any questions and thanks for reading!
Member for
3 years 9 monthsLong time mobile team lead with a love for network engineering, security, IoT, oss, writing, wireless, and mobile. Avid runner and determined health nut living in the greater Chicagoland area.
Comments
Great job!
Although the problem looks complex, you have made it look really simple with the algorithm. Really great job man!
Thank you very much, Andre!
Thank you very much, Andre!