素数等差数列

先写测试数据是个好习惯。

水一篇

题面

输入a,b

输出a,b间所有长度超过3的素数等差数列,每行输出一个

本来觉得有比较简易的方法来计算,但是最后还是暴力了。

素数相关的规律并不好找,考虑到这个机试并不会那么难,所以能暴力就暴力吧。

代码如下:

#include <cstdio>
#include <iostream>
#define MAXN 1000000
using namespace std;
/*
4 30
// 5 7 11 13 17 19 23 29
5 17 29
5 11 17 23 29
7 13 19
11 17 23 29
17 23 29
*/
bool prime[MAXN];
void is_prime(int n)
{
    fill(prime, prime + MAXN, true);
    prime[1] = false;
    for (int i = 2; i <= n / 2; i++)
    {
        if (prime[i])
        {
            for (int j = 2; j * i <= n; j++)
            {
                prime[i * j] = false;
            }
        }
    }
    // for (int i = 0; i < n; i++)
    // {
    //     if (prime[i])
    //     {
    //         cout << i << " ";
    //     }
    // }
}

int main()
{
    int a, b;
    cin >> a >> b;
    if (a > b) // 防止a比b大
    {
        a = a + b;
        b = a - b;
        a = a - b;
    }

    is_prime(b);
    for (int j = a; j <= b; j++) // 枚举首项
    {
        if (!prime[j]) // 剪枝,首项非素赶快滚
        {
            continue;
        }

        for (int i = 2; i <= b - j; i += 2) // 枚举等差
        {
            int length = 0;
            int k = j;
            for (; k <= b; k += i)
            {
                if (!prime[k]) // 当这一项不是素数的时候,说明这个等差数列到头了
                {
                    break;
                }
                length++;
            }
            if (length >= 3) // 善后
            {
                for (int t = k - i * length; t < k; t += i)
                {
                    cout << t << " ";
                }
                cout << "\n";
            }
        }
    }
    return 0;
}
Subscribe
提醒
guest
0 评论
Inline Feedbacks
View all comments