Проверка на мультипростое число - C (СИ)

Формулировка задачи:

Доброго времени суток! Попыталась найти что-то подобное на форуме - не нашла (очень сложно сформулировать поисковый запрос по проблеме). Сама уже вторые сутки ломаю голову (понимаю, что не срок. Однако препод бьет копытом, брызжет слюной и ругается).

Задача

Требуется написать программу, которое будет выводить, является ли введенное с клавиатуры число "мультипростым". Под "мультипростым" числом понимается

простое

число, которое либо состоит из одной цифры (3, 5...), либо которое можно разбить на простые и/или мультипростые составляющие. Под разбивкой понимается отделение скольких бы то ни было

левых

цифр числа от остальных. Сложно объяснить, проще показать на примере: Число 7523. Само по себе число 7523 простое. Возможны три варианта разбивки: 7 523 75 23 752 3 7 - простое число. 523 - тоже просто и может быть разбито на 5 23 или 52 3. Пять - простое число. Двадцать три - тоже, причем, два и три - тоже простые. Т.е. возможен как минимум один вариант, что это число "мультипростое" => тру. Программа должна

обязательно

содержать две функции: нерекурсивную

int is_prime(int num)

(которая возвращает 1, если число простое, и 0 - в обратном случае)

и рекурсивную int is_multi_prime(int num)

(которая возвращает 1, если число "мультипростое", и 0 - в обратном случае). Если кому нужно, я могу выслать оригинал задания (на английском языке). Ко всему прочему, есть ограничения, установленные преподавателем: "вы должны использовать только то, что мы уже прошли на занятиях. и ни в коем случае то, что мы еще не прошли". Так что массивы, строки, классы - использовать нельзя. По сути, можно использовать только функции и рекурсию.

Мои соображения по поводу решения.

(это можно не читать, если само задание понятно и решение его очевидно) я, честно говоря, уже запуталась в своих размышлениях. И получившийся говнокод кидать не буду (ибо стыдно). В любом случае, is_prime - это просто.

{
  int i;
  for( i=2; i*i<=num; i++)
  {
    if (num%i ==0) 
      return 0;
  }
  return 1;
}

Также, я еще создала функцию, которая считает количество цифр в введенном числе. Она используется в дальнейшем для разделения числа. Если мы хотим отделить первое число, то num1 = num\10^(n-1) - первая цифра ("7" в примере) num2 = num%10^(n-1) - все остальное("523" в примере) на входе функция is_multi_prime в первую очередь проверяет целое ли введенное число вообще (если нет, значит сразу же 0), потом разделяет его по первой цифре. Если первая цифра - прайм, то функция рекурсивно вызывается опять с параметром num2. В принципе, у меня получилось добиться того, что 7523 - мультипрайм. И даже пара самых простых непраймов и не мультипраймов давали правильные значения. Но как только числа стали четырехзначными, все посыпалось. Более того, я ни малейшего понятия не имею, как запихнуть проверку следующего разделения, если первое не прошло (например, 2311 - простое число. два - не простое, но 23 и 11 - простые, 2 и 3, 1 и 1 - простые). Ну в смысле, я могу русским/английским языком описать алгоритм, но не могу его описать на Си.

З.ы,

Думаю, меня вполне устроит подробный алгоритм на русском/английском, но если будет разобранный код - будет лучше. Также, могу скинуть скетч блок-схемы, конкретно лекции/семинары по курсу и т.п. Спасибо!!

Решение задачи: «Проверка на мультипростое число»

Листинг программы

#include <stdio.h>
 
int is_prime(unsigned n) {
    unsigned i;
    
    if ( n < 2 )
        return 0;
    
    for ( i = 2; i * i <= n; ++i )
        if ( ! ( n % i ) )
            return 0;
    return 1;
}
 
unsigned pow_10(unsigned pwr) {
    return ( pwr ) ? 10 * pow_10(pwr - 1) : 1;
}
 
unsigned num_digits(unsigned n) {
    return ( n > 9 ) ? 1 + num_digits(n / 10) : 1;
}
 
int is_multi_prime(unsigned n) {
    unsigned div = pow_10(num_digits(n));
    
    if ( n < 10 )
        return is_prime(n);
    
    while ( ( div /= 10 ) > 9 ) 
        if ( ! is_prime(n / div) || ! is_prime(n % div) )
            return 0;
    
    return 1;
}
 
#define LIMIT 1000000
 
int main(void) {
    unsigned n;
    
    for ( n = 1; n < LIMIT; ++n )
        if ( is_multi_prime(n) )
            printf("%u\n", n);
    
    return 0;
}

Объяснение кода листинга программы

Включаем стандартную библиотеку ввода-вывода
Определяем функцию is_prime, которая проверяет простое ли число (проверка на делимость без остатка)
Определяем функцию pow_10, которая вычисляет число 10 в степени (с использованием рекурсии)
Определяем функцию num_digits, которая вычисляет количество цифр числа (с использованием рекурсии)
Определяем функцию is_multi_prime, которая проверяет число на мультипростоту (проверка на деление без остатка на все числа от 10 до 999)
В функции main инициализируем переменную n со значением 1
В цикле от 1 до LIMIT (предварительно определенного ограничения) вызываем функцию is_multi_prime и выводим результат (если число мультипростое)
Завершаем программу с возвращаемым значением 0