Question:

How to calculate sum of primes factors for each number with C++

Summary

Let’s assume:

Two parameters- ‘a’, ‘b’

Private Function- getPoints

Public function- sumofPowers

Solution

private:

// TC : O((b-a+1) * sqrt(num) * log(num)) ~= O(b*sqrt(b)*log(b)) where max. 'num' could be 'b'

// SC : O(1)

int getPoints(int num) {

int points = 0;

int temp = num;

for (int i = 2; i*i <= num; i++) {

while(num % i == 0) {

num /= i;

points++;

}

if (num != 1) {

points++;

}

return points;

}

public:

int sumOfPowers(int a, int b){

int res = 0;

for (int i = a; i <= b; i++) {

res += getPoints(i);

}

return res;

}

Explanation

The function getPoints(int num) determines how many prime factors there are for a given integer num.
The function iterates through potential divisors (i) using a loop, determining whether they divide num. For every divisor found, a points counter is increased.
The sum of the prime factors for each number in the range [a, b] is determined by the public member function sumOfPowers(int a, int b).
To determine the prime factor to count for each number, it calls the private function getPoints(i) after iterating through each number in the range.