|
|
|
|
|
|
by sold
4142 days ago
|
|
|
Unary representation is useless when speaking about complexity in number theory. If you take a number N given in unary, convert it to binary and do trial division up to the square root, it will take O(N log N) time for conversion to binary and O(sqrt(N) * log(N)^2) for trial division (depending on your computational model, it could be O(N) and O(sqrt(N)) - I am counting bit complexity). In total, it's O(N log N). The runtime is dominated by reading the input! The complexity of trial division and the brilliant AKS algorithm is the same from this viewpoint. Even if you had an algorithm that did not have to convert to binary and could tell in time linear to unary represenation whether a number is prime, it would be interesting trivia but nothing worthy a Nobel prize. In practice numbers are given in binary (or some other base>1 number system). To use your algorithm, you would have to convert to unary, which already means trial division would be faster. |
|
|