We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
If n<2, then it is 1 and has no primes. Otherwise, 2 is the smallest prime we start with ("count" of primes = 1). Prod is an ongoing multiple of the primes. As long as this number times the next possible prime (+2, only odd numbers greater than 2 are prime) is less then the original number, then we continue running the loop (the reason for this is similar to the explaination for euclidean algorithm given below).
Since the prod contains all of the previously obtained primes (multiplied together), then if the gcd == 1 (between prod and the "new" number), then that means that the "new" number is also prime, as none of the other primes (contained in prod) go into it. Therefore, we multiply it into our prod and continue onward, increasing the count. Once the for condition exceeds the original number, we have the full count and return that.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Leonardo's Prime Factors
You are viewing a single comment's thread. Return to all comments →
If n<2, then it is 1 and has no primes. Otherwise, 2 is the smallest prime we start with ("count" of primes = 1). Prod is an ongoing multiple of the primes. As long as this number times the next possible prime (+2, only odd numbers greater than 2 are prime) is less then the original number, then we continue running the loop (the reason for this is similar to the explaination for euclidean algorithm given below).
Since the prod contains all of the previously obtained primes (multiplied together), then if the gcd == 1 (between prod and the "new" number), then that means that the "new" number is also prime, as none of the other primes (contained in prod) go into it. Therefore, we multiply it into our prod and continue onward, increasing the count. Once the for condition exceeds the original number, we have the full count and return that.