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: asaleotestf@gmail.com
  • Telegram Messenger: https:/t.me/tommytran0401

Quảng cáo việc làm

 

Thích hợp các bạn nữ mảng thợ may làm việc tại nước NGA

Đơn hàng Tuyển dụng 100 Thợ may đi Nga(đợt 1 tháng 3.2021, đợt 2 tháng 5.2021). Lương thực lãnh 800 USD, bao ăn ở, vé máy bay và visa, phí xuất cảnh(1800 USD)trả khi đi làm có lương. Bạn có thể liên hệ CÔNG TY qua Phone/Zalo: (+84) 944 225 212. Công ty sẽ tư vấn cho bạn.

Xem chi tiết: >>> https://bit.ly/3o9NOfR

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

 
Facebook công bố Scrapbook: góc nhỏ cha mẹ

Facebook công bố Scrapbook: góc nhỏ cha mẹ

Mới đây, Facebook đã chính thức tung ra tính năng Scrapbook, cho phép các bậc phụ huynh tạo ra một album ảnh riêng

Giải pháp performance cho việc update lượt xem hiệu quả

Đối với một website có nhiều lượt truy cập hằng ngày, giải pháp nào để việc update lượt xem cho từng bài viết cụ thể để không gây ảnh hưởng đến performance của cả hệ thống.

 

Quảng cáo Google Adwords để thử nghiệm từ khóa

Quảng cáo Google Adwords để thử nghiệm từ khóa

Các web bán hàng trên Internet của các doanh nghiệp hiện nay đang là kênh tiếp xúc với khách hàng rất hiệu quả và chi phí bỏ ra khá thấp. Vì vậy doanh nghiệp nào cũng muốn web của mình lên top Google để có nhiều khách hàng.