Showing posts from July, 2014

The Ultimate Primality Test

Figuring out whether or not a number is prime has been a long quest by mathematicians and computer scientists, especially in the last 50 years with the development of computer cryptography, in particular the RSA algorithm. The common, centuries-old method for checking whether a number N is prime is very straightforward: test all the numbers "i" between 2 and SQRT(N), and if N is divisible by "i" then N is not prime, otherwise it is prime. There is a number of optimizations to this algorithm, but its core remains the same, and so does the lower bound execution time of O(SQRT(N)). Which works well for N = 32212254719, since SQRT(N) ~= 179478. However - try this: N = 225251798594466661409915431774713195745814267044878909733007331390393510002687. This is a special prime number, one of the Woodall prime numbers . Out of curiosity, its root square is 4.74606994E38, which becomes intractable. What are the options? The best primality test algorithm was actually discovere

Is this number a perfect square?

When solving an algorithm problem, the size of the input will likely dictate the approach to be taken to solve it. For the following problem: "determine whether the number N is a perfect where N is <= 1,000,000. You can't use the SQRT operator", you can solve it by writing a simple O(N) loop. However, if the problem statement has N equals to this number: 165427932084831047046609078136342385692486778784193040575415275237601141991915477442845407673976779988232591513989058207150 467947523250038046743349535213521742642331376230769593309027187809744543689481194688348037467758678555486040607128113607782 083765614731180084729138856439466527641625533551140106381117226415600300034739904992269491478944475237827791509015498086952 540122244942342301906037349725404262930038509928927062527110279498414480102632727349285397856356384385317530337640402344225 257713111998890184844181150362794164888726083850881120857078821273038738588588961135056057777457454067942853805232017960397 0509