Điểm nguyên tố (điểm chia số thành hai số nguyên tố) trong C++

Trong bài toán này, chúng ta được cho một số N. Nhiệm vụ là in ra tất cả các điểm nguyên tố của số đó, in -1 nếu không có điểm nguyên tố nào.

Điểm nguyên tố là các chỉ số chia số thành hai số nguyên tố, một ở bên trái và một ở bên phải.

Hãy xem ví dụ sau để hiểu rõ vấn đề:

Input: 2359 Output: 1

Giải thích: khi chia số tại chỉ số 1, ta được 2 và 59 - cả hai đều là số nguyên tố.

Để giải quyết, ta kiểm tra xem có thể chia trái-phải cho số đó không. Nếu hợp lệ, ta thử tất cả các tổ hợp số có thể tạo ra và kiểm tra xem chúng có phải số nguyên tố hay không. Nếu là số nguyên tố, in ra chỉ số.

Đoạn mã dưới đây minh họa triển khai giải pháp:

Ví dụ

#include <bits/stdc++.h> using namespace std; int countDigits(int n) {    int count = 0;    while (n > 0){       count++;       n = n/10;    }    return count; } int checkPrime(int n) {    if (n <= 1)       return -1;    if (n <= 3)       return 0;    if (n%2 == 0 || n%3 == 0)       return -1;    for (int i=5; i*i<=n; i=i+6)       if (n%i == 0 || n%(i+2) == 0)          return -1;    return 0; } void primePoints(int n) {    int count = countDigits(n);    if (count==1 || count==2){       cout << "-1";       return;    }    bool found = false;    for (int i=1; i<(count-1); i++){       int left = n / ((int)pow(10,count-i));       int right = n % ((int)pow(10,count-i-1));       if (checkPrime(left) == 0 && checkPrime(right) == 0){          cout<<i<<"\t";          found = true;       }    }    if (found == false)    cout << "-1"; } int main() {    int N = 2359;    cout<<"Tất cả các phép chia nguyên tố của số "<<N<<" là :\n";    primePoints(N);    return 0; }

Kết quả

Tất cả các phép chia nguyên tố của số 2359 là : 1