c++ - 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

我会这样写程序

#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 的计算值比应有的少 1，因为您没有考虑 bar[i] 已经是质数。

初始设置 seq 等于 1。

int seq = 1;

此外，您错误地确定了质数。例如，根据您的算法，1 是素数。