Phân tích thừa số nguyên tố

Thuật toán phân tích thừa số nguyên tố

Chức năng: Phân tích số nguyên n thành các thừa số nguyên tố

Chương trình:

#include <bits/stdc++.h>

using namespace std;

vector<int> p, alpha;

void Factor(int n) {

  if ((n<=1000000 && isPrime[n]) || (n>1000000 && IsPrime(n) == true)) {

    p.push_back(n); alpha.push_back(1);

    return;

  }

  int i=0;

  while (n>1) {

    while ((i<primes.size()) && (n%primes[i]!=0)) i++;

    if (i==primes.size()-1) {

      p.push_back(n); alpha.push_back(1);

      return;

    }

    int count=0;

    while (n%primes[i] == 0) {

      count++; 

      n = n/primes[i];

    }

    p.push_back(primes[i]); alpha.push_back(count);

    if ((n<=1000000 && isPrime[n])) {

      p.push_back(n); alpha.push_back(1);

      return;

    }

  }

}