Tìm số thứ N chỉ chứa các chữ số nguyên tố (2,3,5,7) bằng C++

Mô tả bài toán

Dãy số chỉ chứa chữ số 2,3,5,7: 2,3,5,7,22,23,25,27,32,33... Tìm số thứ N.

Ví dụ

N=6 → Output: 23.

Giải thuật

Xem như hệ cơ số 4 (chữ số 0,1,2,3 ↔ 2,3,5,7).\n1. Tìm độ dài L của số thứ N: tổng 4¹+4²+...+4ᴸ ≥ N.\n2. Xác định từng chữ số từ trái sang phải bằng cách so sánh N với ranh giới của từng chữ số.

Mã nguồn C++

#include <iostream>
#include <cmath>
using namespace std;

void findNthNumber(int n) {
    long len=1, last=0;
    while (true) {
        long curr = last + pow(4, len);
        if (last < n && curr >= n) break;
        len++; last = curr;
    }
    for (int i=1; i<=len; i++) {
        for (int d=1; d<=4; d++) {
            if (last + pow(4, len-i) < n) last += pow(4, len-i);
            else {
                cout << (d==1?'2':d==2?'3':d==3?'5':'7');
                break;
            }
        }
    }
}

int main() {
    int N=32;
    cout << N << "th prime-digit number: ";
    findNthNumber(N);
    return 0;
}

Đầu ra

32th number made of prime digits is 257