Sum product puzzle

A third party picks two integers, X and Y, each from the interval 2 to 99, and tells Mr. Sam the sum of the two integers, and Mr. Paul the product of the two. Sam and Paul do not know the values given to the other. Paul tells Sam, “I do not know the two integers.” Sam tells Paul, “I know you didn’t. Neither do I.” Paul replies, “Oh, now I know the integers.” Sam replies back, “Now I know too.”

Given that both of them are telling the truth, what are the two integers.
Continue reading

Sieve of Eratosthenes: Finding all primes below a limit N

In number theoretic algorithmic problems, there arises cases where you need to find all primes below a certain limit, say N. The improved trial division primality check algorithm can be used to find all primes below a certain limit that isn’t too large. But with larger limits, there is a need for a more efficient way. Sieve of Eratosthenes is a 2000 year old algorithm for doing just that, in an efficient manner.
Continue reading