โปรแกรม C++ แยกตัวประกอบเฉพาะของจำนวนที่กำหนด

นี่คือโปรแกรม C++ เพื่อหาการแยกตัวประกอบเฉพาะ (unique factorization) ของจำนวนเต็มที่กำหนด โดยที่ผลรวมของการแบ่งส่วนนั้นได้จำนวนเต็ม โปรแกรมนี้จะสร้างวิธีการแทนจำนวนเต็มบวก n เป็นผลรวมของจำนวนเต็มบวกทั้งหมดที่เป็นไปได้

อัลกอริทึม

Begin function displayAllUniqueParts(int m):
  1) กำดัชดัชนีขององค์ประกอบสุดท้าย k ใน partition เป็น 0
  2) เริ่มต้น partition แรกเป็นตัวเลขเอง p[k] = m
  3) สร้าง while loop ที่พิมพ์ partition ปัจจุบันก่อน แล้วสร้าง partition ถัดไป ลูปหยุดเมื่อ partition ปัจจุบันเป็น 1 ทั้งหมด
  4) แสดง partition ปัจจุบันด้วย displayArray(p, k + 1)
  5) สร้าง partition ถัดไป:
     เริ่มต้น val = 0
     หาค่าที่ไม่ใช่ 1 ตัวสุดท้ายทางขวาใน p[] อัปเดต val ด้วย
     ถ้า k < 0 ทุกค่าเป็น 1 ไม่มี partition อีก
     ลด p[k] ที่หาได้ และปรับ val
  6) ถ้า val มากกว่า ลำดับเรียงจะถูกละเมิด แบ่ง val เป็นค่าขนาด p[k] คัดลอกค่าเหล่านี้หลัง p[k]
  7) คัดลอก val ไปตำแหน่งถัดไป และเพิ่มตำแหน่ง
End

ตัวอย่างโค้ด

#include <iostream>
using namespace std;

void displayArray(int p[], int m) {
  for (int i = 0; i < m; i++)
    cout << p[i] << " ";
  cout << endl;
}

void displayAllUniqueParts(int m) {
  int p[m];
  int k = 0;
  p[k] = m;
  while (true) {
    displayArray(p, k + 1);
    int val = 0;
    while (k >= 0 && p[k] == 1) {
      val += p[k];
      k--;
    }
    if (k < 0)
      return;
    p[k]--;
    val++;
    while (val > p[k]) {
      p[k + 1] = p[k];
      val = val - p[k];
      k++;
    }
    p[k + 1] = val;
    k++;
  }
}

int main() {
  cout << "Display All Unique Partitions of 3\n";
  displayAllUniqueParts(3);
  cout << "\nDisplay All Unique Partitions of 4\n";
  displayAllUniqueParts(4);
  cout << "\nDisplay All Unique Partitions of 5\n";
  displayAllUniqueParts(5);
  return 0;
}

ผลลัพธ์

Display All Unique Partitions of 3
3
2 1
1 1 1
Display All Unique Partitions of 4
4
3 1
2 2
2 1 1
1 1 1 1
Display All Unique Partitions of 5
5
4 1
3 2
3 1 1
2 2 1
2 1 1 1
1 1 1 1 1