Boris Coding Blog

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

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