ในปัญหานี้ เราได้รับตัวเลข N หน้าที่ของเราคือพิมพ์จุดเฉพาะทั้งหมดของตัวเลข มิฉะนั้นให้พิมพ์ -1 หากไม่มีจุดสำคัญ
คะแนนพิเศษ คือค่าดัชนีที่แยกตัวเลขออกเป็นสองจำนวนเฉพาะ ตัวแรกอยู่ทางซ้ายและอีกตัวอยู่ทางขวา
มาดูตัวอย่างทำความเข้าใจปัญหากัน
Input: 2359 Output: 1
คำอธิบาย :เมื่อแยกตัวเลขที่ดัชนี 1 เราจะได้ 2 และ 59 เป็นจำนวนเฉพาะสองตัว
เพื่อแก้ปัญหานี้ เราจะตรวจสอบว่ามีการแบ่งซ้าย-ขวาสำหรับตัวเลขหรือไม่ หากถูกต้อง เราจะลองผสมตัวเลขทั้งหมดที่สามารถสร้างได้และตรวจสอบว่าเป็นจำนวนเฉพาะหรือไม่ หากเป็นจำนวนเฉพาะ ให้พิมพ์ดัชนี
โค้ดด้านล่างแสดงการใช้งานโซลูชันของเรา
ตัวอย่าง
#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<<"All prime divisions of number "<<N<<" are :\n";
primePoints(N);
return 0;
} ผลลัพธ์
All prime divisions of number 2359 are : 1
