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

 
6 Drupal SEO Modules Required for Superior Search Ranking Performance

6 Drupal SEO Modules cần thiết cho hiệu suất xếp hạng website

If you are running your site with Drupal, you are reaping the numerous benefits this publishing platform has to offer.

Number 3: Performance - 5 lổi cần tránh trong Drupal Website

Number 3: Performance - 5 lổi cần tránh trong Drupal Website

Performance is crucial for providing a great user experience. If the site is slow or balky, even great functionality won’t keep the site visitor engaged.

Google bán Motorola Home cho Arris với giá 2,35 tỉ USD

Google bán Motorola Home cho Arris với giá 2,35 tỉ USD

Sau khi có một số hành động cho hoạt động tái cơ cấu Motorola Mobility, Google tiếp tục bán Motorola Home, một chi nhánh của Motorola Mobility, cho Arris với giá 2,35 tỉ USD.

Tomdesgin.vn

 

Drupal Services