Если нужно проверить а) точно, и б) одно; в) не очень большое число (миллион тоже небольшое) — ничего нет лучше, чем проверка нечётных чисел до корня из n. То есть до 1000.
Если точно, много и небольшие — то придётся держать список простых чисел, пополняя его, когда попадётся слишком большое число. Список тоже до корня из n. Допустим, если предел — int4 (≈4 млрд), то нужно держать только список до 65535, это пара тысяч чисел.
Если число совсем небольшое и может быть где-то в списке — ищем его хитрой разновидностью поиска: проверяем 1-е число, 2-е, 4-е и т.д., пока не определим диапазон, где может быть число. И в этом диапазоне ищем двоичным поиском.
В криптографии востребован неточный поиск — «число, скорее всего, простое». Но об этом не будем, вы не настолько круты. Тут уже основано на том, что держим таблицу небольших простых чисел и делим на них, а затем гоняем неточные тесты.
PERFECT number — это СОВЕРШЕННОЕ число. Это не то (сумма всех делителей равняется самому числу), и для теста на совершенное число тоже надо проверять до корня из n — если a делится на b, то добавляем и b, и a/b (кроме случаев, когда b=1 и b²=a, разумеется). Если есть простые числа до корня из n — тоже можно разбить на простые множители (один из множителей может быть больше корня из n!) и подключить комбинаторику, чтобы заполучить остальные.
