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

Question

I came across an interesting problem. The input is a number from 1..n, where n <= 10^9. So you need to make a prime number out of it by changing its digits. Moreover, you need to change as few digits as possible, and if there are several such options, then you need to minimize the number. For, example 10, answer is 11.

This task passed all my tests and was accepted in the checking system. But my decision seems strange and quackish.

I considered a few cases on small numbers, and considering that prime numbers occur quite often, I decided to iterate over one digit of the number first and replace it with any from 0..9. But this solution fell on the 5th test. After that, I decided to add a search of the second digit and then the solution passed the tests.

It turns out that my solution works for the asymptotic len(n)^281sqrt(n). Which is good. But I absolutely cannot prove why 2 digits is enough. And suddenly there are some numbers where you need to replace 3 digits or more.

Please help me figure out why this is true, or help me come up with some kind of normal solution.

#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

I think this can be explained by a few observations/factors.

1. Most centuries (xxxx00 to xxxx99) have at least one prime.
2. The first century without a prime is 1671800.
3. The first millenium without a prime is 13893290219204000 (which is sufficiently greater than 10^9).

If you combine these factors, it's easy to see why most numbers can be made prime by changing two digits (since a large number of centuries have primes). And if the century doesn't have a prime, then changing three digits is guaranteed to give a solution, since each millenium in the given range has a prime number.