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: 6 (2 votes)
Ảnh của Tommy Tran

Tommy Tran 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
  • Phone/Zalo: (+84) 944 225 212
  • WhatsApp: (+84) 944 225 212
  • Line Messenger: (+84) 944 225 212
  • Email: [email protected]
  • Telegram Messenger: https:/t.me/tommytran0401

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

 
Android

Thị trường ưa chuộng Android hơn Windows Phone

Sau vụ kiện Samsung - Apple đình đám mà nạn nhân gián tiếp là Android, một số hãng smartphone Android đang tìm phương án thay thế dù vẫn tuyên bố gắn bó với nền tảng của Google.

13 gotcha giúp bạn sử dụng và developing trong Drupal land

13 gotcha giúp bạn sử dụng và developing trong Drupal land

Half a year ago I wrote a blog post about various stumble blocks I had run into in my first year as a Drupal developer

Headless Drupal? 6 Resources quan trọng cần biết

Headless Drupal? 6 Resources quan trọng cần biết

It's a big upgrade, no question. If you're like me, however, you may prefer a completely custom frontend crafted out of HTML, CSS and JavaScript

BLOG POSTS

 

Wordpress Freelancer

 

Wordpress Freelancer