логика такая же как и в линейном решете Эратосфена,почитать можно тут e-maxx.ru/algo/prime_sieve_linear
как я понел задачу примерно решается она так http://pastebin.com/byXSB0v7
,сложность алгоритма будет примерно N * log M (M - это количество чисел в куче , кстати если будет тайм лимит подправьте меня 
это изза излишних чисел в куче которые заведомо больше чем нужное нам,но это думаю исправимо ,сейчас просто времени нет додумывать но логика примерно такая кажется)