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

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

在这次重写中我...

avoided using namespace std;.
删除了 unnecessary/confusing 个变量。
使用了明确的变量名称（bar 仅当名称无关紧要时才应在示例代码中使用）。
将 is_prime 移动到它自己的函数中。

但是这段代码有一些突出的问题。应该...

如果用户指定数组长度 > 100，请使用 vector instead of an array. As it stands, it's vulnerable to a buffer overflow attack。
使用 faster method of finding primes。我们只需要检查数字的平方根，可以跳过很多数字，比如 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

将数组转换为布尔数组并找出最长的长度。试试这个片段（未优化）：

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

C++如何从数组中获取最长的素数序列

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

c++

primes

loops

for-loop

while-loop