algorithm - 给定范围内有多少个 PR 编号？

Question

这不是作业问题。我只是对这个问题感到好奇。我的方法很简单:-)

我的暴力破解 C++代码:

int main()
{
    ll l,r;
    cin>>l>>r;
    
    ll f=0;
    ll i=l;
    
    while(i<=r)
    {
        ll j=0;
        string s;
        ll c=0;
        s=to_string(i);

        // cout<<s<<" ";

        ll x=s.length();

        if(x==1)
        {
            c=0;
        }
        else 
        {
            j=0;
            //whil
            while(j<=x-2)
            {
                string b,g;

                b="1";
                g="1";
                
                b=s[j];
                g=s[j+1];
                
                ll k1,k2;
                
                k1=stoi(b);
                k2=stoi(g);

                if(__gcd(k1,k2)==1)
                {
                    c=1;
                    break;
                }
                
                j++;
            }
        }
        
        ll d=0;
        j=0;
        while(j<=x-1)
        {
            if( s[j]=='2' || s[j]=='3' || s[j]=='5' || s[j]=='7')
            {
                string b;
                b="1";
                b=s[j];
                ll k1=stoi(b);
                if(i%k1==0)
                {
                    //d=0;
                }
                else
                {
                    d=1;
                    break;
                }
            }
            j++;
        }
        if(c==1 || d==1)
        {
            // cout<<"NO";
        }
        else
        {
            f++;
            // cout<<"PR";
        }
        // cout<<"\n";
        
        i++;
    }
    
    cout<<f;
    
    return 0;
}

You are given 2 integers 'L' and 'R' . You are required to find the count of all the PR numbers in the range 'L' to 'R' inclusively. PR number are the numbers which satisfy following properties:

1. No pair of adjacent digits are co-prime i.e. adjacent digits in a PR number will not be co-prime to each other.

2. PR number is divisible by all the single digit prime numbers which occur as a digit in the PR number.

Note: Two numbers 'a' and 'b' are co-prime, if gcd(a,b)=1.

Also, gcd(0,a)=a;

Example:
Input: [2,5].
Output: '4'.

(Note: '1' is not a prime-number, though its very common)

(All the integers: '2','3','4','5') satisfy the condition of PR numbers :-)

约束“L”、“R”:1 <= L, R <= 10^18

解决这个问题最有效的算法是什么？

Answer 1

注意:这将仅解决第 1 部分，即没有一对相邻数字是互质的，即 PR 数字中的相邻数字不会彼此互质。

这是 python 中的一种建设性方法:我们不会遍历范围内的所有数字并按条件过滤，而是构造所有满足条件的数字。请注意，如果我们有一个有效的数字序列，为了使它继续有效，只有最右边的数字很重要才能决定下一个数字是什么。

def ways(max_number, prev_digit, current_number):
    if current_number > max_number:
        return 0
    count = 1
    if prev_digit == 0:
        if current_number != 0:
            count += ways(max_number, 0, current_number * 10)
        for i in range(2, 10): 
            count += ways(max_number, i, current_number * 10 + i)
    if prev_digit == 2 or prev_digit == 4 or prev_digit == 8:
        for i in [0, 2, 4, 6, 8]:
            count += ways(max_number, i, current_number * 10 + i)
    if prev_digit == 3 or prev_digit == 9:
        for i in [0, 3, 6, 9]:
            count += ways(max_number, i, current_number * 10 + i)
    if prev_digit == 5 or prev_digit == 7:
        count += ways(max_number, 0, current_number * 10)
        count += ways(max_number, prev_digit, current_number * 10 + prev_digit)
    if prev_digit == 6:
        for i in [0, 2, 3, 4, 6, 8, 9]:
            count += ways(max_number, i, current_number * 10 + i)
    return count

由于我们要生成最大为 max_number 的所有有效数字而没有任何重复，因此此函数的复杂度为 O(0 和 max_number 之间满足条件 1 的数字的数量)。要计算 a 到 b 的范围，我们只需要执行 ways(b) - ways(a - 1)。

从 0 到 100 万计算这些数字用时不到 1 秒，因为只有 42935 个数字满足结果。由于满足条件的数字很少，因此我们可以检查它们是否是其素数的倍数以满足条件 2。我将这部分留给读者，因为有多种方法可以做到这一点。