Как получить самую длинную последовательность простых чисел из массива в c ++

Question

Я пытаюсь получить самую длинную (самую большую) последовательность последовательных простых чисел из массива ..

При первом тесте с 10 элементами в массиве работает, но когда я попробовал с 15 элементами, как:3, 5, 7, 8, 9, 11, 13, 17, 19, 20, 23, 29, 31, 37, 41 это выплевывает 4, что неверно.

#include <iostream>
using namespace std;

int main()
{
    int bar[100];
    int x, j = 0;

    int maxseq = 0;
    int longestseqstart = 0;
    cout << "How big is the array? =";
    cin >> x;
    for (int i = 0; i < x; i++) {
        cout << "bar[" << i << "]=";
        cin >> bar[i];
    }
    for (int i = 1; i < x - 1; i = j) {
        int startseq = i;
        int seq = 0;

        j = i + 1;
        bool prim = true;
        int a = bar[i];
        for (int d = 2; d <= a / 2; d++) {
            if (a % d == 0) {
                prim = false;
            }
        }
        while (j < x && prim) {
            seq++;
            if (seq > maxseq) {
                maxseq = seq;
                longestseqstart = i;
            }
            int a = bar[j];
            for (int d = 2; d <= a / 2; d++) {
                if (a % d == 0) {
                    prim = false;
                }
            }
            j++;
        }
    }

    cout << "The longest sequence is: ";
    cout << maxseq;

    return 0;
}

Answer 1

Преобразовать массив в логический массив и найти самую длинную длину. Попробуйте этот фрагмент (не оптимизирован):

bool is_prime(int n) {
    for (int i = 2; i < n; i++) {
        if (n%i == 0) return false;
    }
    return true;
}

int main() {
    //Input
    unsigned int bar[15] = { 3, 5, 7, 8, 9, 11, 13, 17, 19, 20, 23, 29, 31, 37, 41 };
    // Convert input to boolean array
    bool boo[15];
    for (int i = 0; i < 15; i++) {
        boo[i] = is_prime(bar[i]);
    }
    //Check the longest boolean array
    int longest = 0;
    for (int i = 0; i < 15; i++) {
        int count = 0;

        while (boo[i + count] && (i+ count) <15) {
            count++;            
        }
        if (longest < count) longest = count;

    }
    //Output
    cout << longest;

    return 0;
}

Answer 2

Алгоритм выглядит в принципе нормально. Проблема главным образом в организации: способ установки блока внутреннего цикла означает, что последовательность простых чисел будет короткой на 1, поскольку самая длинная последовательность обновляется только в начале внутреннего цикла, пропуская конечное простое число.

Несколько минимальных неудачных примеров:

How big is the array? =1
bar[0]=13
The longest sequence is: 0

How big is the array? =2
bar[0]=5
bar[1]=6
The longest sequence is: 0

Обратите внимание, что повторная первичная проверка выполняется в двух местах. Этого не должно быть. Если мы переместим всю простую логику в цикл и протестируем новую самую длинную последовательность только после завершения всего цикла, у нас будет четкий, точный алгоритм:

#include <iostream>

int is_prime(int n) {
    for (int i = 2; i <= n / 2; i++) {
        if (n % i == 0) {
            return false;
        }
    }

    return true;
}

int main() {
    int nums[100];
    int n;
    std::cout << "How big is the array? =";
    std::cin >> n;

    for (int i = 0; i < n; i++) {
        std::cout << "nums[" << i << "]=";
        std::cin >> nums[i];
    }

    int longest = 0;

    for (int i = 0, start = 0; i < n; i++) {
        for (start = i; i < n && is_prime(nums[i]); i++);

        longest = std::max(longest, i - start);
    }

    std::cout << "The longest sequence is: " << longest;
    return 0;
}

В этом перезаписи I .. .

• исключено using namespace std;.
• удалены ненужные / сбивающие с толку переменные.
• использованы чистые имена переменных (bar должно быть толькоиспользуется в примере кода, когда имя не имеет значения).
• перемещено is_prime в свою собственную функцию.

Но с этим кодом есть нерешенные проблемы. Следует ...

• использовать vector вместо массива. В существующем состоянии он уязвим для атаки переполнения буфера , если пользователь указывает длину массива> 100.
• использует более быстрый метод поиска простых чисел . Нам нужно только проверить квадратный корень числа и пропустить много чисел, например, четные числа после 2. Я подозреваю, что это случайное упражнение, но стоит упомянуть.
• переместите longest_prime_sequence к отдельной функции (и, возможно, к сбору пользовательского ввода).

Answer 3

Я бы написал программу следующим образом

#include <iostream>
#include <iterator>
#include <algorithm>

bool is_prime( unsigned int n )
{
    bool prime = n % 2 == 0 ? n == 2 : n != 1;

    for ( unsigned int i = 3; prime && i <= n / i; i += 2 )
    {
        prime = n % i != 0;
    }

    return prime;
}


int main() 
{
    unsigned int a[] =  { 3, 5, 7, 8, 9, 11, 13, 17, 19, 20, 23, 29, 31, 37, 41 };
    const size_t N = sizeof( a ) / sizeof( *a );

    size_t maxseq = 0;

    for ( auto current = std::find_if( a, a + N, is_prime ); 
          current != a + N;
          current = std::find_if( current, a + N, is_prime ) )
    {
        auto first = current;
        current = std::find_if_not( current, a + N, is_prime );

        size_t n = std::distance( first, current );

        if ( maxseq < n ) maxseq = n;
    }

    std::cout << "The longest sequence is: " <<  maxseq << '\n';

    return 0;
}

Вывод программы:

The longest sequence is: 5

Я не использовал универсальные функции std::begin( a ) и std::end( a ), потому что в вашей программемассив может содержать меньше фактических элементов, чем размерность массива.

Если вы еще не знаете, стандартные алгоритмы C ++, тогда программу можно определить следующим образом:

#include <iostream>

bool is_prime( unsigned int n )
{
    bool prime = n % 2 == 0 ? n == 2 : n != 1;

    for ( unsigned int i = 3; prime && i <= n / i; i += 2 )
    {
        prime = n % i != 0;
    }

    return prime;
}


int main() 
{
    unsigned int a[] =  { 3, 5, 7, 8, 9, 11, 13, 17, 19, 20, 23, 29, 31, 37, 41 };
    const size_t N = sizeof( a ) / sizeof( *a );

    size_t maxseq = 0;
    size_t n = 0;

    for ( size_t i = 0; i < N; i++ )
    {
        bool prime = a[i] % 2 == 0 ? a[i] == 2 : a[i] != 1;

        for ( unsigned int j = 3; prime && j <= a[i] / j; j += 2 )
        {
            prime = a[i] % j != 0;
        }

        if ( prime )
        {
            if ( maxseq < ++n ) maxseq = n;
        }
        else
        {
            n = 0;
        }
    }

    std::cout << "The longest sequence is: " <<  maxseq << '\n';

    return 0;
}

Выход программы

The longest sequence is: 5

Что касается вашей программы, то этот цикл

for (int i = 1; i < x - 1; i = j) {

пропускает первый элемент массива bar[0].

И благодаря этому утверждению

j = i + 1;

расчетное значение seq на единицу меньше, чем должно быть, поскольку вы не учитываете, что bar[i] уже является простым.

Первоначально установите seq равным 1.

int seq = 1;

Более того, вы неправильно определяете простые числа. Например, согласно вашему алгоритму 1 простое.

Answer 4

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

#include <iostream>
#include <vector>
using namespace std;

bool isPrime(int a) {
    bool prim = true;
    for (int d = 2; d*d <= a; ++d) {
        if (a % d == 0) {
            prim = false;
        }
    }
    return prim;
}

int main()
{
    int x;

    int longestseqstart = 0;
    cout << "How big is the array? =";
    cin >> x;
    std::vector<int> bar(x);
    for (int i = 0; i < x; i++) {
        cout << "bar[" << i << "]=";
        cin >> bar[i];
    }

    unsigned int count = 0;
    unsigned int maxseq = 0;
    for (const auto &el : bar) {
        if (isPrime(el)) {
            ++count;
            if (count > maxseq) maxseq = count;
        } else count = 0;
    }
    cout << "The longest sequence is: ";
    cout << maxseq;

    return 0;
}

Конечно, вы можете избежать использования std::vector и функций с

#include <iostream>
using namespace std;

int main()
{
    int x;

    int longestseqstart = 0;
    cout << "How big is the array? =";
    cin >> x;
    int bar[100];
    for (int i = 0; i < x; i++) {
        cout << "bar[" << i << "]=";
        cin >> bar[i];
    }

    unsigned int count = 0;
    unsigned int maxseq = 0;
    for (unsigned int i = 0; i < x; ++i) {
        int a = bar[i];
        bool prim = true;
        for (int d = 2; d*d <= a; ++d) {
            if (a % d == 0) {
                prim = false;
            }
        }
        if (prim) {
            ++count;
            if (count > maxseq) maxseq = count;
        } else count = 0;
    }
    cout << "The longest sequence is: ";
    cout << maxseq;

    return 0;
}