Найти количество разложений данного натурального числа на простые слагаемые - 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? Пожалуйста, подскажите, уже просто сил нет никаких.

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

textual
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)

8   голосов, оценка 3.750 из 5


СОХРАНИТЬ ССЫЛКУ