Tìm chuối số nguyên tố, bằng giải thuật đệ quy C/C++

Tìm chuối số nguyên tố, bằng giải thuật đệ quy C/C++

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;

}
Bạn thấy bài viết này như thế nào?: 
Average: 7.3 (3 votes)
Ảnh của Tommy Tran

Tommy owner Express Magazine

Drupal Developer having 9+ year experience, implementation and having strong knowledge of technical specifications, workflow development. Ability to perform effectively and efficiently in team and individually. Always enthusiastic and interseted to study new technologies

  • Skype ID: tthanhthuy

Advertisement

 

jobsora

Dich vu khu trung tphcm

Dich vu diet chuot tphcm

Dich vu diet con trung

Quảng Cáo Bài Viết

 
the tin dung

Các thuật ngữ về tài khoản, thẻ ATM, thẻ tín dụng trong ngân hàng

Khi bắt đầu đi học hoặc đi làm, nhiều bạn sẽ ra ngân hàng làm một cái thẻ ATM để nhận và rút tiền. Tuy nhiên khi nhận thẻ về, nhiều bạn có thể bỏ qua

Thủ thuật customized cho Drupal Slideshow

Thủ thuật customized cho Drupal Slideshow

So a client wants a slideshow. No problem! Oh, they want full WYSIWYG for the captions. No problem. What about an option to let a user grab embed code

How to Check Your Facebook Account is Hacked or Not

How to Check Your Facebook Account is Hacked or Not

Has Your Facebook Account Been Hacked? Today here we will let you know How to Check Your Facebook Account is Hacked or Not.

Công ty diệt chuột T&C

 

Diet con trung