Найти количество разложений данного натурального числа на простые слагаемые - QBasic

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

Здравствуйте всем! У меня на руках задача, над которой вот уже какую неделю голову ломаю. Решать её надо либо на QBasic, либо на Pascal (знаю только QBasic). Условие такое: "Любое целое число большее 1 можно единственным способом представить в виде произведения простых множителей. Но если попытаться представить целые числа в виде суммы простых слагаемых, то таких разложений окажется несколько. Например, для числа 11 есть 6 таких разложений: 11=11, 11=2+2+7, 11=3+3+5, 11=3+3+5, 11=2+2+2+5, 11=2+3+3+3, 11=2+2+2+2+3. Напишите программу, которая вводит с клавиатуры натуральное число N (1<N<=5000) и выводит на экран количество разложений данного числа на простые слагаемые". Так вот, я решаю на QBasic, но самый простой алгоритм, который я только мог придумать тормозит компьютер даже при числе N=100, не говоря уже о 5000! Значит, тут нужен кардинально другой подход. Она рассчитана на гения? Или просто её сложно решить именно в QBasic? Пожалуйста, подскажите, уже просто сил нет никаких.

Решение задачи: «Найти количество разложений данного натурального числа на простые слагаемые»

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

DIM i AS LONG, j AS LONG, k AS LONG, n AS LONG
DIM a(5000) AS DOUBLE, b(1 TO 669) AS LONG
n = 100 'n >= 2 and n <= 5000
 
'заполняем массив b() простыми числами
b(1) = 2 'первое простое число - 2
b(2) = 3
k = 2 'счетчик простых чисел
FOR i = 5 TO n STEP 2 'вычисляем все простые числа до n, перебираем нечетные числа
FOR j = 2 TO k 'проверку деления на 2 исключаем
    IF i MOD b(j) = 0 THEN EXIT FOR
    IF b(j) * b(j) > i THEN
        k = k + 1 'увеличиваем счетчик простых чисел
        b(k) = i 'запоминаем простое число
        EXIT FOR
    END IF
NEXT j, i
 
'вычисляем количество вариантов динамическим программированием
a(0) = 1
FOR i = 1 TO k
FOR j = b(i) TO n
    a(j) = a(j) + a(j - b(i))
NEXT j, i
PRINT a(n)

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

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

Переменные:
- i, j, k, n (целые числа)
- a(5000), b(1 TO 669) (массивы)
Задаются начальные значения:
- n = 100 (заданное число)
- b(1) = 2 (первое простое число)
- b(2) = 3 (второе простое число)
- k = 2 (счетчик простых чисел)
Циклы для поиска простых чисел:
- Первый вложенный цикл: i = 5 TO n STEP 2 (перебирает нечетные числа, начиная с 5 и заканчивая n, с шагом 2)
- Второй вложенный цикл: j = 2 TO k (перебирает простые числа от 2 до k)
Условие для проверки числа на простоту:
- Если i MOD b(j) = 0 (тест на деление без остатка), то цикл прерывается
- Если b(j) * b(j) > i (проверка на квадрат простого числа), то увеличивается счетчик простых чисел и значение записывается в массив b
Вычисление количества разложений числа n на простые множители:
- a(0) = 1 (изначальное значение)
- Затем, в цикле от 1 до k, для каждого простого числа b(i), значение a(j) увеличивается на a(j - b(i)) (так как каждое простое число может быть множителем числа n)
Вывод результата:
- PRINT a(n) (выводится значение a(n), которое и является количеством разложений числа n на простые множители)