[Bài toán] Chuỗi số nguyên tố.

Trong chuối số nguyên tố thì chữ số đầu tiên là số nguyên tố, số đến chữ số thứ n là số nguyên tố. Để hiểu hơn ta sét ví dụ sau:
Số 7331 là chuỗi số nguyên tố có 4 chữ số, trong đó chữ số đầu tiên (7) là số nguyên tố, số đến chữ số thứ 2 (73) là số nguyên tố, số đến chữ số thứ 3 (733) là số nguyên tố, và số đến chữ số thứ 4 (7331) là số nguyên tố.
Yêu cầu: Hãy liệt kê tất cả các chuỗi số nguyên tố có độ dài n.
[Input]
Dữ liệu đầu vào được chứa trong file Input.txt.
Dòng đầu ghi số lượng test case. Các dòng sau là test case tương ứng. Trong mỗi test case ghi số chữ số của chuỗi số.
[Output]
Kết quả của chương trình được ghi ra file Output.txt ,tương ứng với mỗi test case ghi ra chuỗi số nguyên tố, các chuỗi số này được ghi tương ứng nên mỗi dòng.
Kết quả của từng test case được ngăn cách bởi một dòng trắng.
[Input example]
5
1
2
3
4

5
[Output example]
2
3
5
7

23
29
31
37
53
59
71
73
79

233
239
293
311
313
317
373
379
593
599
719
733
739
797

2333
2339
2393
2399
2939
3119
3137
3733
3739
3793
3797
5939
7193
7331
7333
7393

23333
23339
23399
23993
29399
31193
31379
37337
37339
37397
59393
59399
71933
73331
73939
[Giải thuật]
*Chuỗi số nguyên tố có độ dài n được tạo thành nhờ phép ghép các chữ số (0,1,2,3,4,5,6,7,8,9). Nhưng vì số đến chữ số thứ i (1 <= i <= n) là số nguyên tố nên ta loại bỏ các chữ số (0,2,4,6,8), khi đó chuỗi số nguyên tố chỉ còn được tạo ra bằng việc ghép các chữ số (1,3,5,7,9).
*Để tìm chuối số nguyên tố, bằng giải thuật đệ quy ta điền từng vị trí i (1 <= i <= n) sao cho số được tạo thành đến chữ số i là số nguyên tố.
*Giải thuật kết thúc khi ta đã tìm đủ n chữ số cho chuỗi số nguyên tố.
Chương trình cài đặt.

#include<iostream>
using namespace std;
int primeNumber[6] = {1,2,3,5,7,9};
int digitLength;
bool isPrime(int n){
 if(n == 2 || n == 3) return true;
 if(n==1 || n%2 == 0 || n%3 == 0) return false;
 int k=-1;
 do{
  k+=6;
  if(n%k == 0 || n%(k+2) == 0) break;
 }while(k*k<n);
 return k*k > n;
}
void find(int index, int previousValue){
 if(index == digitLength){
  cout<<previousValue<<"\n";
  return;
 }
 for (int loop = 0;loop <6; loop ++){
  int value = previousValue*10+ primeNumber[loop];
  if(isPrime(value)){
   find(index+1,value);
  }
 }
}
int main(){
 freopen("Input.txt","r",stdin);
 freopen("Output.txt","w",stdout);
 int t;
 cin>>t;
 for(int i=1;i<=t;i++){
  cin>>digitLength;
  find(0,0);
  cout<<"\n";
 }
 return 0;
}

Cám ơn bạn đã đọc bài viết này. Hãy chia sẻ bài viết và bình luận ý kiến của bạn ở bên dưới.

Share this

Chào mừng bạn đến với SimpleCodeCJava Blog - Mục đích của chúng tôi khi thành lập blog này là muốn chia sẻ những kiến thức và kinh nghiệm lập trình mà chúng tôi đã học được với mong muốn giúp đỡ mọi người, giúp bạn rút ngắn được thời gian tìm hiểu cũng như việc giải quyết những vấn đề trong lập trình C và Java.