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.
Observe that if a number is composite, it must have a prime factor less than or equal to its square root.
Proof:
0. Let r be a composite number.
1. Assume that prime number q divides r. Let n x n = r, i.e. n is the square root of r. If q < n, we are done.
2. Now suppose that q > n. By assumption r/q is a whole number, and we know that either r/q is prime, or r/q has prime factors of its own.
3. But n = r/n, and r/n > r/q, and r/q > { any prime factors of r/q }, so clearly there exists a prime factor of r smaller than the square root of r, as desired.
This means you only need to create an array of ~46340 booleans (square root of 2 x 10^9) and apply the prime sieve to find the primes in that list. Using that list for your trial divisors will give better time complexity than O(sqrt(n)).
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Time Complexity: Primality
You are viewing a single comment's thread. Return to all comments →
Observe that if a number is composite, it must have a prime factor less than or equal to its square root.
Proof:
0. Let r be a composite number.
1. Assume that prime number q divides r. Let n x n = r, i.e. n is the square root of r. If q < n, we are done.
2. Now suppose that q > n. By assumption r/q is a whole number, and we know that either r/q is prime, or r/q has prime factors of its own.
3. But n = r/n, and r/n > r/q, and r/q > { any prime factors of r/q }, so clearly there exists a prime factor of r smaller than the square root of r, as desired.
This means you only need to create an array of ~46340 booleans (square root of 2 x 10^9) and apply the prime sieve to find the primes in that list. Using that list for your trial divisors will give better time complexity than O(sqrt(n)).