[MallSerg]

Решето Эратосфена.

Легких путей определения что число является простым нету. Только честная проверка каждого числа.
На сложности задачи разложения числа на простые множители и держится современная криптография и алгоритмы хеширования.