-
Notifications
You must be signed in to change notification settings - Fork 0
/
hybrid ULL (high range).cpp
211 lines (179 loc) · 5.24 KB
/
hybrid ULL (high range).cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
// hybrid program
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <map>
#include <vector>
#include <list>
typedef unsigned long long int ULL;
using namespace std;
// map to store prime factors of a number with their powers
map< ULL, ULL> factors;
map< ULL, ULL> :: iterator itr;
// function to store the factors in the map and their powers
void createMap(ULL n)
{
if(factors.find(n) == factors.end())
factors[n]=1;
else
factors[n]++;
}
// function to store prime factors of a number in the map
void primeFactors(ULL n)
{
// divide the number by 2 untill it bcomes the odd number
while (n%2==0)
{
createMap(2);
n = n/2;
}
// find the prime factors of a number which are from 3 onwards
for (ULL i=3; i*i<=n; i=i+2)
{
while (n%i==0)
{
createMap(i);
n = n/i;
}
}
// number left with no factors
if (n>2)
createMap(n);
}
// function to get sum of divisors of a number
void divisorsSum()
{
ULL sum=1;
for( itr=factors.begin(); itr!=factors.end(); itr++)
{
sum = sum * ( (pow(itr->first,itr->second+1)-1)/(itr->first-1) );
}
cout<<"sum of divisors : "<<sum<<"\n";
}
// function to get the divisors of a number using prime factors of a number
void getDivisors( ULL row_size)
{
// dimensions of 2D array
row_size += 1;
ULL total_row = factors.size();
// 2D array created
ULL ** a = new ULL*[total_row];
for ( int i=0; i<total_row; i++)
{
a[i] = new ULL[row_size];
fill_n(a[i],row_size,0);
}
// to store the powers of prime factors in the 2D array
ULL row=0;
for( itr=factors.begin(); itr!=factors.end(); itr++)
{
for( ULL j=0; j<=itr->second; j++)
{
a[row][j] = pow(itr->first,j);
}
row++;
}
// create a temp vector of size = row_size with each element is 1
vector<ULL> temp(row_size,1);
// final output vector
vector<ULL> divisors;
vector<ULL> :: iterator itr1;
// perform operations on the 2D matrix to get all the divisors of the number
for(ULL i=0; i<total_row; i++)
{
for(ULL j=0; j<row_size; j++)
{
for(ULL k=0; k<temp.size(); k++)
{
divisors.push_back(a[i][j]*temp.at(k));
}
}
// sort and remove the duplicates from the vector
sort(divisors.begin(),divisors.end());
divisors.erase( unique( divisors.begin(), divisors.end()), divisors.end());
// clear the previous vector
temp.clear();
// store the resulted vector in temp vector
temp.assign(divisors.begin(),divisors.end());
}
// to remove the 0 form the divisors list if present
if(divisors.at(0) == 0)
divisors.assign(divisors.begin()+1, divisors.end());
// display the divisors of the number
//cout<<"divisors are : \n";
//for(ULL i=0;i<divisors.size();i++)
// cout<<divisors.at(i)<<" ";
// display count of the divisors of the number
cout<<"\ncount of divisors : "<<divisors.size();
}
// function to get the count of numbers less than n and relative prime to it
void eulersFunction()
{
ULL count=1;
for( itr=factors.begin(); itr!=factors.end(); itr++)
{
count = count * ( (pow(itr->first,itr->second-1))*(itr->first-1) );
}
cout<<"\ncount of number less than number and relative prime to it : "<<count<<"\n";
}
// function to get the euler set elements
void getEulerElements(ULL n)
{
// final output list
list<ULL> reduced_residue_set;
// non relative prime list
list<ULL> non_relative_prime;
list<ULL> :: iterator itr2;
// store the numbers from 2 to n-1 in the output list
for(ULL i=2; i<n; i++)
reduced_residue_set.push_back(i);
// store the number which are multiples of prime factors of n and less than n in the non_relative_prime
for(itr=factors.begin(); itr!=factors.end(); itr++)
{
ULL temp=itr->first;
while(temp<n)
{
non_relative_prime.push_back(temp);
temp+=itr->first;
}
}
// to remove the duplicates from the non_relative_prime list
non_relative_prime.sort();
non_relative_prime.unique();
// remove the non_relative_prime from the reduced_residue_set
for(itr2=non_relative_prime.begin(); itr2!=non_relative_prime.end(); itr2++)
reduced_residue_set.remove(*itr2);
// insert 1 in the reduced_residue_set
reduced_residue_set.push_front(1);
// display the elements of the reduced_residue_set
for(itr2=reduced_residue_set.begin(); itr2!=reduced_residue_set.end(); itr2++)
cout<<*itr2<<" ";
// display size of reduced_residue_set
cout<<"\ncount (for verification) : "<<reduced_residue_set.size();
}
int main()
{
ULL n,max_power=0;
cin>>n;
// get the prime factors of a number
primeFactors(n);
// print the prime factors of a number and get the maximum power
cout<<"Prime factors are : \n";
for( itr=factors.begin(); itr!=factors.end(); itr++)
{
if(itr->second > max_power)
max_power = itr->second;
cout<<itr->first<<" : "<<itr->second<<"\n";
}
// for sum of divisors of a number
divisorsSum();
// get the divisors of a number using prime factors of a number
getDivisors(max_power);
// get the count of numbers less than n and relative prime to it
eulersFunction();
// get euler set elements ( cannot be called because of very big number)
//getEulerElements(n);
return 0;
}