1. The problem statement, all variables and given/known data Given a number N<=1018, I need to find the largest prime number less than or equal to N 2. Relevant equations 3. The attempt at a solution I can only think of a brute-force solution i.e. iterate from N in decreasing order until you get a prime number. And to check if number is prime just iterate till its square-root. If it has no factors then it is prime else its not. But this won't work as Nmax = 1018 which will take too much time. Any ideas?