lena71
Save Scummer
2
MONTHS
2 2 MONTHS OF SERVICE
LEVEL 1
200 XP
We'll see how you can factorize a natural number, using vector and pair from the C++ STL!
First, you need the following declarations:
The pairs will contain:
- first element is the DIVISOR
- second element is the EXPONENT
Having these settled, let's move on to reading the number and starting the factorization! We will begin by computing the exponent of 2, because after having 2 as a divisor (in case the number is even), the other divisors are in the form of (2N+1), where N>=1 and N is a natural number.
If we have 2 as a divisor, we add it to our vector. Then, we move on to the next divisors and calculate all exponents simply! This is done like this:
This is a pretty simple method, we try with any good divisor and always increase the divisor by 2, to ensure it is (2N+1). We also set the number of divisors back to zero on every new try - this is very important!
Then, we need the output:
To avoid confusion or ugly output, such as an extra '*' in the end, we have created a bool variable and we always output the '*' at the beginning of the for loop. If you don't add it like that, you will see a wrong output or need to use control character '\b' to remove the unwanted characters.
The output is simple, as we use an iterator to loop through the vector. Due to the way we computed the factors, they are already sorted from low to high.
The full main.cpp source code is here:
The output will be something like this:
x = 120
120 = 2^3 * 3^1 * 5^1
Enjoy!
Download
First, you need the following declarations:
- #include <iostream>
- #include <vector>
- #include <utility>
- using
namespace
std;
- vector<
pair<
int
, int
>
>
factors;
- int
n;
The pairs will contain:
- first element is the DIVISOR
- second element is the EXPONENT
Having these settled, let's move on to reading the number and starting the factorization! We will begin by computing the exponent of 2, because after having 2 as a divisor (in case the number is even), the other divisors are in the form of (2N+1), where N>=1 and N is a natural number.
- n =
0
;
- cout
<<
" x = "
;
- cin
>>
x;
- int
x_original =
x;
- int
div
=
2
;
- int
nrd =
0
;
- while
(
x %
2
==
0
)
{
- nrd++
;
- x /
=
2
;
- }
- if
(
nrd >
0
)
{
- factors.push_back
(
make_pair(
2
, nrd)
)
;
- }
If we have 2 as a divisor, we add it to our vector. Then, we move on to the next divisors and calculate all exponents simply! This is done like this:
- div
=
3
;
- while
(
x >
1
)
{
- nrd =
0
;
- while
(
x %
div
==
0
)
{
- x /
=
div
;
- nrd++
;
- }
- if
(
nrd >
0
)
{
- factors.push_back
(
make_pair(
div
, nrd)
)
;
- }
- div
+
=
2
;
- }
This is a pretty simple method, we try with any good divisor and always increase the divisor by 2, to ensure it is (2N+1). We also set the number of divisors back to zero on every new try - this is very important!
Then, we need the output:
- bool
first =
true
;
- vector<
pair<
int
, int
>
>
::
iterator
it;
- cout
<<
endl <<
x_original <<
" = "
;
- for
(
it =
factors.begin
(
)
;
it !
=
factors.end
(
)
;
it++
)
{
- if
(
first ==
false
)
{
- cout
<<
" * "
;
- }
else
{
- first =
false
;
- }
- cout
<<
(
*
it)
.first
<<
"^"
<<
(
*
it)
.second
;
- }
To avoid confusion or ugly output, such as an extra '*' in the end, we have created a bool variable and we always output the '*' at the beginning of the for loop. If you don't add it like that, you will see a wrong output or need to use control character '\b' to remove the unwanted characters.
The output is simple, as we use an iterator to loop through the vector. Due to the way we computed the factors, they are already sorted from low to high.
The full main.cpp source code is here:
- #include <iostream>
- #include <vector>
- #include <utility>
- using
namespace
std;
- vector<
pair<
int
, int
>
>
factors;
- int
n;
- int
main(
int
argc, char
**
argv)
{
- int
x;
- n =
0
;
- cout
<<
" x = "
;
- cin
>>
x;
- int
x_original =
x;
- int
div
=
2
;
- int
nrd =
0
;
- while
(
x %
2
==
0
)
{
- nrd++
;
- x /
=
2
;
- }
- if
(
nrd >
0
)
{
- factors.push_back
(
make_pair(
2
, nrd)
)
;
- }
- div
=
3
;
- while
(
x >
1
)
{
- nrd =
0
;
- while
(
x %
div
==
0
)
{
- x /
=
div
;
- nrd++
;
- }
- if
(
nrd >
0
)
{
- factors.push_back
(
make_pair(
div
, nrd)
)
;
- }
- div
+
=
2
;
- }
- bool
first =
true
;
- vector<
pair<
int
, int
>
>
::
iterator
it;
- cout
<<
endl <<
x_original <<
" = "
;
- for
(
it =
factors.begin
(
)
;
it !
=
factors.end
(
)
;
it++
)
{
- if
(
first ==
false
)
{
- cout
<<
" * "
;
- }
else
{
- first =
false
;
- }
- cout
<<
(
*
it)
.first
<<
"^"
<<
(
*
it)
.second
;
- }
- cout
<<
endl;
- return
0
;
- }
The output will be something like this:
x = 120
120 = 2^3 * 3^1 * 5^1
Enjoy!
Download
You must upgrade your account or reply in the thread to view the hidden content.