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.
For any fixed N, there exists a set of witnesses such that Miller-Rabin with those fixed bases will correctly identify all composite numbers less than N. This removes the element of randomness from Miller-Rabin, and the set of fixed bases is actually surprisingly small for N = 2^64.
If N^(1/3) < x < N and x is not divisible by any prime < N^(1/3), then x is the product of either one or two primes larger than N^(2/3). In either case, you don't need to factor it completely. If x is a square, how many distinct prime divisors does it have? And how many divisors total? If x is not a square, how many divisors does it have? And how many divisors total?
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Nice Clique
You are viewing a single comment's thread. Return to all comments →
Some hints if you are stuck:
For any fixed N, there exists a set of witnesses such that Miller-Rabin with those fixed bases will correctly identify all composite numbers less than N. This removes the element of randomness from Miller-Rabin, and the set of fixed bases is actually surprisingly small for N = 2^64.
If N^(1/3) < x < N and x is not divisible by any prime < N^(1/3), then x is the product of either one or two primes larger than N^(2/3). In either case, you don't need to factor it completely. If x is a square, how many distinct prime divisors does it have? And how many divisors total? If x is not a square, how many divisors does it have? And how many divisors total?