3 ms·
So if you have some lookup tables you can determine if a given number is prime. Up to some maximum based on the size of the tables. And apparently the time to g
by phkahler 12y ago
So if you have some lookup tables you can determine if a given number is prime. Up to some maximum based on the size of the tables. And apparently the time to generate the tables is quadratic in the size of n? Why is this relevant? AKS shows that determining if n is prime can be done in polynomial time - polynomial in log(n), not n. Is there something significant about these 2 sets of primes they talk about?
- wbhart 12y agoYou mean O(sqrt(n)), not quadratic. And given that the most obvious algorithm there is (check every possible divisor up to sqrt(n)) is O(sqrt(n)) arithmetic operations, I think it is fair to say this is not an important result. I suppose it is a constant factor better than sqrt(n). But tricks along these lines go back to Gauss, at least. Edit: ah I see, they claim O(n^2). Well I've never had an O(n^2) primality test before. I will put that in my kit of "do-not-ever-use-this" tools, just in case all my other ones break.