AlgoDaily Primes

 Today's AlgoDaily problem is to find the sum of prime numbers that come before the parameter number n. 

I thought of a solution that is similar to the Fibonacci sequence dynamic programming solution. The idea is to populate a list of primes as you march through 3...n (we seed the prime sequence with 2). You take out the multiples of the current prime from the range list as you go, thereby making your solution more efficient. So you check if the current prime divides the numbers in the current range list (the list of the all the remaining numbers obtained after taking out the multiples of all the previous primes) and take out the numbers that are divisible. The first number in the remaining list is the new prime, because it isn't divisible by any of the primes coming before it. And so you go, the algorithm is as efficient as it can be because prime factorization has exponential complexity.


The solution is here: https://github.com/mariakesa/Algorithms/blob/master/AlgoDaily/AlgorithmsPractice.ipynb

Kommentaarid