How to get the longest sequence of prime numbers from an array in c++

Question

I'm trying to get the longest(largest) sequence of consecutive prime numbers from an array..

On first test with 10 elements in the array works , but when i tried with 15 elements like: 3, 5, 7, 8, 9, 11, 13, 17, 19, 20, 23, 29, 31, 37, 41 it spit out 4, which is incorrect.

#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;
}

It sounds like you may need to learn how to use a debugger to step through your code. With a good debugger, you can execute your program line by line and see where it is deviating from what you expect. This is an essential tool if you are going to do any programming. Further reading: [How to debug small programs](http://ericlippert.com/2014/03/05/how-to-debug-small-programs/) and [Debugging Guide](http://idownvotedbecau.se/nodebugging/) — NathanOliver, Oct 21 '19 at 14:30
`for (int i = 1; i < x-1; i=j) ` what is that line supposed to do ? — Jeffrey, Oct 21 '19 at 14:31
You appear to never look at the first element in the array (though that does not seem to be the root of the error you describe). — 500 - Internal Server Error, Oct 21 '19 at 14:32
This is unrelated, but you can split up the operation on your primality test by changing `for (int d = 2; d <= a / 2; d++) {` to `for (int d = 2; d <= sqrt(a); d++) {` https://codeaccepted.wordpress.com/2013/08/25/algorithm-2-primality-testing/ — Andra, Oct 21 '19 at 14:34
I would suggest to split it into smaller subproblems. You need to determine for each element in the array whether it is a prime number. Once you know this, the rest is as simple as finding the longest sequence of `true` in an array of `bool` — 463035818_is_not_an_ai, Oct 21 '19 at 14:34
@Andra: The usual check involves checking for the square of a number since the `sqrt` function is more time consuming. — Thomas Matthews, Oct 21 '19 at 14:38
Split problem into pieces. Each partial problem should have separate code (function). First problem: finding longest sequence fulfilling unknown condition. Second problem: checking if number is a prime number. Third problem generate list of primes. Forth problem reading data. Fifth problem: printing results. — Marek R, Oct 21 '19 at 14:39
...actually you dont need to know it for every number in the array, eg if you know already that 1st and 3rd is not prime and you know that the last 3 numbers in the array are prime, then you dont need to look at the 2nd, but thats for the next step when you want to get a more optimal algorithm — 463035818_is_not_an_ai, Oct 21 '19 at 14:39
@NathanOliver Thanks, i'm using visual studio but i didn't taught to stop it. formerlyknowas_463035818 i don't know how to work with functions yet :( Marek R don't know how to work with functions sorry.. — Victor Bînzar, Oct 21 '19 at 14:40

score 0 · Answer 1 · answered Oct 21 '19 at 15:04

You are checking twice for prime numbers and you are using a nested loop. That's not necessary. It's enough to read all numbers, check each number, increment the count if it's a prime number and store the maximum sequence length.

#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;
}

Of course you can avoid the usage of std::vector and functions with

#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;
}

ggorlen · Answer 2 · 2019-10-21T15:26:14.857

The algorithm looks basically OK. The issue is mostly one of organization: the way the inner loop block is set up means that a run of primes will be short by 1 because the longest sequence is only updated at the beginning of the inner loop, missing the final prime.

A couple of minimal failing examples are:

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

Note that there's a repeated prime check in two places. This should not be. If we move all of the prime logic into the loop and test for a new longest sequence only after finishing the entire run, we'll have a clear, accurate algorithm:

#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;
}

In this rewrite I...

avoided using namespace std;.
removed unnecessary/confusing variables.
used clear variable names (bar should only be used in example code when the name doesn't matter).
moved is_prime to its own function.

But there are outstanding issues with this code. It should...

use a vector instead of an array. As it stands, it's vulnerable to a buffer overflow attack should the user specify an array length > 100.
use a faster method of finding primes. We only need to check up to the square root of the number and can skip a lot of numbers such as even numbers after 2. I suspect this is incidental to this exercise but it's worth mentioning.
move the longest_prime_sequence to a separate function (and possibly user input gathering as well).

Vlad from Moscow · Accepted Answer · 2019-10-21T16:04:37.963

I would write the program the following way

#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 program output is

The longest sequence is: 5

I did not use generic functions std::begin( a ) and std::end( a ) because in your program the array can contain less actual elements than the array dimension.

If you do not know yet standard C++ algorithms then the program can be defined the following way

#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 program output is the same as above

The longest sequence is: 5

As for your program then this loop

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

skips the first element of the array that is bar[0].

And due to this statement

j = i + 1;

the calculated value of seq one less than it should be because you do not take into account that bar[i] is already prime.

Set initially seq equal to 1.

int seq = 1;

Moreover you incorrectly are determining prime numbers. For example according to your algorithm 1 is prime.

seccpur · Answer 4 · 2019-10-21T16:40:02.780

Convert the array to a Boolean array and find longest length. Try this snippet(not optimized):

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;
}

How to get the longest sequence of prime numbers from an array in c++

4 Answers4