Ето и примерна имплементация на описания алгоритъм:
Оставаме да добавите проверка дали входното число е по-голямо от 1, защото по дефиниция числа като 0, 1, -1 и -2 не са прости.
Тествайте решението си тук: https://judge.softuni.org/Contests/Practice/Index/514#9.