如何想出一个正常的解决方案来解决暴力问题？

Question

我遇到了一个有趣的问题。输入是一个从 1..n 开始的数字，其中 n <= 10^9。所以你需要通过改变它的数字来得到一个质数。此外，您需要更改尽可能少的数字，如果有多个这样的选项，则需要尽量减少数字。例如 10，答案是 11.

这个任务通过了我所有的测试，并在检查系统中被接受。但我的决定似乎很奇怪和庸医。

我考虑了一些小数的情况，考虑到素数经常出现，我决定先迭代数字的一位，然后用 0..9 中的任何数字替换它。但是这个解决方案落在了第5次测试上。之后，我决定添加第二个数字的搜索，然后解决方案通过了测试。

事实证明，我的解决方案适用于渐近 len(n)^281sqrt(n)。哪个好。但我绝对无法证明为什么 2 位数就足够了。突然有一些数字需要替换 3 位数或更多。

请帮我弄清楚这是为什么，或者帮我想出一些正常的解决方案。

#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>

using namespace std;

bool prost(int x)
{
    if (x <= 1)
    {
        return false;
    }
    for (int i = 2; i <= (int)sqrt(x); i++)
    {
        if (x % i == 0)
        {
            return false;
        }
    }
    return true;
}

int main()
{
    string s;

    cin >> s;

    if (prost(stoi(s)))
    {
        cout << s << endl;
        return 0;
    }

    string ans = "";

    for (int i = 0; i < s.length(); i++)
    {
        ans += '9';
    }

    for (int i = 0; i < s.length(); i++)
    {
        for (char j = '0'; j <= '9'; j++)
        {
            if (i == 0 && j == '0')
            {
                continue;
            }
            char buff = s[i];

            s[i] = j;

            if (prost(stoi(s)))
            {
                ans = min(ans, s);
            }

            s[i] = buff;
        }
    }

    string shab = "";

    for (int i = 0; i < s.length(); i++)
    {
        shab += '9';
    }

    if (shab == ans)
    {
        for (int i = 0; i < s.length(); i++)
        {
            for (int j = i + 1; j < s.length(); j++)
            {
                for (char ii = '0'; ii <= '9'; ii++)
                {
                    for (char jj = '0'; jj <= '9'; jj++)
                    {
                        char buff1 = s[i];
                        char buff2 = s[j];
                        if (i == 0 && ii == '0') continue;

                        s[i] = ii;
                        s[j] = jj;

                        if (prost(stoi(s)))
                        {
                            ans = min(ans, s);
                        }

                        s[i] = buff1;
                        s[j] = buff2;
                    }
                }
            }
        }
        if (ans == shab)
        {
            cout << 1 / 0;
            return -0;
        }
    }

    cout << ans << endl;

    return 0;
}

Answer 1

我想这可以用几个observations/factors来解释。

大多数世纪（xxxx00 to xxxx99）至少有一个素数。
没有素数的 first 世纪是 1671800。
没有素数的 first 千禧年是 13893290219204000（比 10^9 足够大）。

如果将这些因素结合起来，就很容易理解为什么大多数数字都可以通过改变两位数变成素数（因为很多世纪都有素数）。如果世纪没有素数，那么改变三位数就可以保证给出一个解决方案，因为给定范围内的每个千年都有一个素数。

如何想出一个正常的解决方案来解决暴力问题？

How to come up with a normal solution to the problem of brute force?

algorithm

numbers

number-theory