Задача с простыми числами - VBA
Формулировка задачи:
Добрый вечер!
Решил поступить в школу программистов Head Hunter, а там при заполнении анкеты дано 5 задач. Не могу эту решить. В универе проходил VBA, поэтому обратился сюда.
Определим функцию P(n,k) следующим образом: P(n,k) = 1, если n может быть представлено в виде суммы k простых чисел (простые числа в записи могут повторяться, 1 не является простым числом) и P(n,k) = 0 в обратном случае.
К примеру, P(10,2) = 1, т.к. 10 может быть представлено в виде суммы 3 + 7 или 5 + 5, а P(11,2) = 0, так как никакие два простых числа не могут дать в сумме 11.
Определим функцию S(n) как сумму значений функции P(i,k) для всех i и k, таких что 1≤i≤n, 1≤k≤n. Таким образом, S(2) = P(1,1) + P(2,1) + P(1,2) + P(2,2) = 1, S(10) = 20, S(1000) = 248838.
Найдите S(10992).
Перебирать я так понимаю не имеет смысла - слишком громоздко. Решил методом исключения действовать. Результат не сходится уже для 1000. Что-то упустил.
Правильное ли направление поиска решения или нет?
Это юзерформа.
Решение задачи: «Задача с простыми числами»
textual
Листинг программы
Sub www() Dim i As Long, j As Long, k As Long, n As Long, l As Long Dim b(1 To 1334) As Long, s As Long, t As Single n = 10992 '1000 t = Timer 'заполняем массив 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 'вычисляем количество вариантов перебором ReDim p(n, n \ 2) As Boolean p(0, 0) = True For l = 1 To n \ 2 For i = 1 To k For j = b(i) + (l - 1) * 2 To n If Not p(j, l) Then If p(j - b(i), l - 1) Then s = s + 1 p(j, l) = True End If End If Next j, i, l Debug.Print s, Timer - t End Sub
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д