Задача с простыми числами - 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

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

9   голосов , оценка 4.333 из 5
Похожие ответы