Created
November 4, 2025 11:46
-
-
Save juanfal/958a9859df5b0452e2063a100f91bb1f to your computer and use it in GitHub Desktop.
prime decomposition
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // primeDecomposition.cpp | |
| // juanfc 2025-11-04 | |
| // https://gist.github.com/juanfal/958a9859df5b0452e2063a100f91bb1f | |
| #include <iostream> | |
| #include <array> | |
| using namespace std; | |
| const int N = 10; | |
| struct TPrime { | |
| int p; | |
| int cnt; | |
| }; | |
| typedef array<TPrime,N> TPrimeDec; | |
| void printPrimeDecomposition(int n, TPrimeDec a); | |
| int main() | |
| { | |
| TPrimeDec primeDecomp(int n); | |
| for (int i = 20000; i < 20100; ++i) { | |
| TPrimeDec r = primeDecomp(i); | |
| if (r[0].cnt > 0) | |
| printPrimeDecomposition(i, r); | |
| } | |
| return 0; | |
| } | |
| TPrimeDec primeDecomp(int n) | |
| { | |
| TPrimeDec r; | |
| int nOfPrimes = 0; | |
| int d = 1; | |
| while (n > 1) { | |
| ++d; | |
| int cnt = 0; | |
| while (n % d == 0) { | |
| n /= d; | |
| ++cnt; | |
| } | |
| if (cnt > 0) | |
| r[nOfPrimes++] = (TPrime){d, cnt}; | |
| } | |
| r[nOfPrimes] = (TPrime){d, 0}; // end mark | |
| return r; | |
| } | |
| void printPrimeDecomposition(int n, TPrimeDec a) | |
| { | |
| cout << n << ": "; | |
| for (int i = 0; a[i].cnt > 0; ++i) | |
| if (a[i].cnt == 1) | |
| cout << a[i].p << " "; | |
| else | |
| cout << a[i].p << "^" | |
| << a[i].cnt << " "; | |
| cout << endl; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment