Нахождение наибольшего просто числа вычеркиванием цифр из заданного с++

[Trifuck]

Собственно задали задачу на динамическое программирование, а я С++ уже подзабыл, а сроки жмут. Собственно вот задача:

Вводится натуральное число, не превосходящее числа 2147 000 000.

Написать программу, которая выдавала бы наибольшее простое число, которое возможно получить из .заданного числа вычеркиванием цифр. Можно вычеркивать любое количество (и ноль тоже) цифр. Если решения нет выдать - число 0.

Ввод: М – число.

Вывод:. число - результат.

Пример:

Ввод: Вывод:

123456 23




З.Ы. Препод также пояснил, что вычеркивать можно не обязательно по краям, то есть при вводе 2121 должно выдавать 11...Заранее спасибо