Каким методом без компа можно проверить число, является ли оно простым?

Будете удивлены: НИКАКИМ. Кроме ручного деления, которое есть то же самое, по-существу.

Формула, дающая "номер" простого числа в последовательности целых чисел покуда так и не найдена. Возможно, её и нет?

Все имеющиеся ныне простые числа определены именно перебором деления кандидата в простое число на числа, меньшие его. Алгоритмы могут быть "тупыми" или изощренными, но сути дела это не меняет. С ЭВМ это, конечно, проще. Но до широкого распространения и удешевления расчётов на ЭЦВМ это было не такое простое дело.

Одна из диссертаций (кажется, самая краткая по изложению и прозрачная по результату) как раз и заключалась в том, что кандидат в течение некоторого времени делил псевдопростое число на другое (кстати, тоже простое число), а аудитория с интересом следила за выкладками.
Когда в итоге получился ответ без дробной части (тоже простое число), докладчика наградили аплодисментами.
И без звука присудили степень.