Найти самую длинную возрастающую цепочку простых чисел - C++ - Ответ 1986473

#include <iostream>
 
int main()
{   
    const int MAX_VALUE = 100500; //максимально возможная цифра
 
    char sieve[ MAX_VALUE ] = { 1, 1 }; //решето Эратосфена
    
    //заполнение решета
    
    for (int i = 2; i < MAX_VALUE ; ++i)
    {
        
        if ( sieve[i] == 0 )
        {
            for ( int j = i * 2 ; j < MAX_VALUE ; j += i )
                sieve[j] = 1;
        }
    }
    
    int arr[] = { 2, 3, 10,5, 6, 7, 3, 5, 7 };
    int size = sizeof( arr ) / sizeof( *arr );
    
    int * dinamic = new int [ size ];
    
    /* 
     * Для каждого члена последовательности находим длину максимальной
     * подпоследовательности, заканчивающейся на этом элементе
     */
    
    dinamic[0] = 0;
    for (int i = 1; i < size ; ++i)
    {
        dinamic[0] = 0;
        
        //если число не простое, последовательность не может оканчиваться на этот элемент
        if ( sieve[ arr[i] ] != 0 )
            continue;
        
        for ( int j = i - 1; j >= 0 ; --j)
            if ( sieve[arr[j]] == 0 && arr[j] < arr[i] )
                dinamic[i] = std::max( dinamic[i], dinamic[j] + 1 );
    }
    
    /*
     * нахождение длины максимальной подпоследовательности и элемента, 
     * на котором она заканчивается
     */
     
    int max = 0, pos = 0;
    for (int i = 0; i < size ; ++i)
    if ( dinamic[i] > max )
    {
        max = dinamic[i];
        pos = i;
    }
    
    //заполнение массива с ответом
    int * answer = new int [ dinamic[pos] + 1];
    
    answer[0] = arr[pos];
    int end = 0;
    
    for (int i = pos - 1, x = pos; i >= 0; --i)
    {
        if ( dinamic[i] + 1 == dinamic[x] )
        { 
            answer[++end] = arr[i];
            x = i;
        }
    }
    
    
    for (int i = end; i >= 0 ; --i)
        std::cout << answer[i] << ' ';
    
    delete[] answer;    
    delete[] dinamic;
}

/*
 * Найти максимальную по длине возрастающую цепочку простых чисел
 */
 
#include <iostream>
 
int main()
{   
    const int MAX_VALUE = 100500; //максимально возможная цифра
 
    char sieve[ MAX_VALUE ] = { 1, 1 }; //решето Эратосфена
    
    //заполнение решета
    
    for (int i = 2; i < MAX_VALUE ; ++i)
    {
        
        if ( sieve[i] == 0 )
        {
            for ( int j = i * 2 ; j < MAX_VALUE ; j += i )
                sieve[j] = 1;
        }
    }
    
    int arr[] = { 2, 3, 3, 5, 6, 7, 3, 5, 7  };
    int size = sizeof( arr ) / sizeof( *arr );
    
    int * dinamic = new int [ size ];
    
    /* 
     * Для каждого члена последовательности находим длину максимальной
     * подпоследовательности, заканчивающейся на этом элементе
     */
    
    dinamic[0] = 0;
    for (int i = 1; i < size ; ++i)
    {
        dinamic[0] = 0;
        
        //если число не простое, последовательность не может оканчиваться на этот элемент
        if ( sieve[ arr[i] ] != 0 )
            continue;
        
        if ( sieve[ arr[i - 1] ] == 0 && arr[i - 1] < arr[i] )
            dinamic[i] = std::max( dinamic[i], dinamic[i - 1] + 1 );
    }
    
    /*
     * нахождение длины максимальной подпоследовательности и элемента, 
     * на котором она заканчивается
     */
     
    int max = 0, pos = 0;
    for (int i = 0; i < size ; ++i)
    if ( dinamic[i] > max )
    {
        max = dinamic[i];
        pos = i;
    }
    
    //заполнение массива с ответом
    for (int i = pos - dinamic[pos] ; i <= pos ; ++i)
        std::cout << arr[i] << ' '; 
    
    delete[] dinamic;
}