Recall: Fundamental Theorem Of Arithmetic
floor(sqrt(b)) - ceil(sqrt(a)) + 1 to calculate all perfect square numbers between a and b.Power of p in n! = floor(n/p) + floor(n/p^2) + floor(n/p^3)..... till p^k > n. We can also calculate prime signature by finding out the exponents for each prime starting from 2 till p <= sqrt(n).Time = O(n)
void printDivisors(int n)
{
for (int i = 1; i <= n; ++i) //till n
{
if(n % i == 0)
cout << i << " ";
}
}
Efficient Approach: Suitable for finding sum of divisors (Aliquot Sum) as it does not print divisors in ascending order.
Time = O(โn)
void printDivisors(int n)
{
for (int i = 2; i*i <= n; ++i) //till sqrt(n)
{
if(n % i == 0)
{
if(i*i == n) cout << i << " "; //for cases like, n=16, i and (n/i) both will be 4, we print only one
else cout << i << " " << (n/i) << " ";
}
}
cout << 1; //don't forget the 1
}
Aliquot Sum:
int sumDiv(int n)
{
int sum = 0;
for (int i = 2; i * i <= n; ++i)
{
if (n % i == 0)
{
if (i * i == n) sum += i;
else sum += i + (n / i);
}
}
return sum + 1; //as we started loop from 2 to avoid adding n itself
}
Sieve Based Method:
Time = O(len) where len is the number of divisors, and
Space = O(MAX)
const int MAX = 1e5;
vector<int> divisor[MAX + 1]; //array of vectors
void divisorSieve()
{
for (int i = 1; i <= MAX; i++)
{
for (int j = i; j <= MAX; j += i)
{
divisor[j].push_back(i);
}
}
}
void printDiv(int n)
{
for (int j = 0; j < divisor[n].size(); j++)
{
cout << divisor[n][j] << " ";
}
}
int main() {
int n = 10;
//cin >> n;
divisorSieve();
printDiv(n);
}
Time = O(โn)
void printPrimeFactors(int n)
{
for(int i = 2; i*i <= n; i++)
{
while(n % i == 0) //removing every i from n
{
cout << i << " ";
n /= i;
}
}
if(n > 1) cout << n; //the largest factor is prime itself
}
Link: https://www.geeksforgeeks.org/prime-factorization-using-sieve-olog-n-multiple-queries/
The idea is to store the Smallest Prime Factor (SPF) for every number in a separate array. Then to calculate the prime factorization of the given number by dividing the given number repeatedly with its smallest prime factor till it becomes 1 and storing the quotient in every step. Those quotients are prime factors of the number.
void factorSieve(int n, bool* s, int* spf)
{
s[0] = s[1] = false;
spf[1] = 1;
for (int i = 2; i <= n; i++) //notice i<=n
{
if (s[i])
{
spf[i] = i; //change
for (int j = i * i; j <= n; j += i)
{
s[j] = false;
if (spf[j] == -1) spf[j] = i; //change
}
}
}
}
int main()
{
int n;
cin >> n;
bool s[n + 1];
int spf[n + 1];
memset(s, true, sizeof(s));
memset(spf, -1, sizeof(spf));
factorSieve(n, s, spf);
//main logic
while (n != 1)
{
cout << spf[n] << " ";
n /= spf[n];
}
return 0;
}
Link: https://www.geeksforgeeks.org/pollards-rho-algorithm-prime-factorization/
Prime Signature - https://mathworld.wolfram.com/PrimeSignature.html
Link: https://www.handakafunda.com/number-system-concepts-for-cat-even-factors-odd-factors-sum-of-factors/