Version 1

bool IsPrime(int num)
{
	if(num<=1)
		return false;
	for(int i=2; i<num; i++)
	{
		if(num%i==0)
			return false;
	}
	return true;
}

We can optimize this function by noticing that we only need to check divisibility for values of i that are less or equal to the square root of num. And if we couldn’t find a divisor under the square root it is impossible mathematically to find another one above the square root because divisors of any number come in couples, the multiplication of any two couples will be the original number. For example 64 has the following divisors:
1           64
2           32
4            16
8           (8)
note here is a special case because 64 has a perfect square root (8) so, while checking the divisors we have to check up to the square root itself.

Version 2

bool IsPrime(int num)
{
	if(num<=1)
		return false;
	for(int i=2; i<=sqrt(num*1.0); i++)
	{
		if(num%i==0)
			return false;
	}
	return true;
}

sqrt() function needs you to include “math.h” file and it takes one double parameter so I multiply our int by 1.0

Another optimization is to realize that there are no even primes greater than 2. Once we’ve checked that n is not even we can safely increment the value of i by 2. We can now write the final method for checking whether a number is prime:

Version 3

bool IsPrime(int num)
{
	if(num<=1)
		return false;
	if(num==2)
		return true;
	if(num%2==0)
		return false;
	for(int i=3; i<=sqrt(num*1.0); i+=2)
	{
		if(num%i==0)
			return false;
	}
	return true;
}

the check in line 5 returns true if the number is 2 because we returns false for all even numbers after it.

I used the following project to test the time needed to check if the numbers from 0 to 100000 are prime or not:

#include <iostream>
#include <time.h>
#include <math.h>

using namespace std;

bool IsPrime(int num)
{
	//past one of the previos versions
}

void main()
{
	clock_t start,end;
	start=clock();
	for(int i=0; i<=100000; i++)
		IsPrime(i);
	end=clock();
	cout<<"Version 1 takes "<<end-start<<" msec"<<endl;

}

And I got:

from 7328 milliseconds to 47 milliseconds. That is awesome , isn’t it ?

int SumOfDivisors(int num)
{
	int sum=0;
	for(int i=1; i<=num; i++)
	{
		if(num%i==0)
		{
			sum+=i;
		}
	}
	return sum;
}

However, this method would become both tedious and difficult for large numbers like 158943609.
Using time.h functions and the following test main we can see that the previous function returns the sum of factors of 158943609 after 2734 msec

void main()
{
clock_t start,end;
int ans=0;
start = clock();
ans = SumOfDivisors(158943609);
end = clock();
printf("%d\n%d msec\n",ans,(end-start));
}

There is a simple and elegant method at hand.
Now look what happens when we list the proper divisors of say 64:
Here they are:
1              64

2              32

4               16

8               (8)
They come in nice pairs so that their product is 64. When we found one of the two in fact we know the other. Special care is needed because 64 is a perfect square: 8 is found twice. To find all pairs we need only to check up to
A second improvement comes from the fact that odd numbers cannot have even numbers as divisors. (The converse is not true: even numbers can have odd divisors).

int SumOfDivisors(int num)
{
	int sum=0;
	int r=floor(sqrt((double)num));
	if(r*r==num) //case that n is a perfect square
	{
		sum += r;
		r -= 1;
	}
	if( num%2 != 0 ) //number is odd
		for(int i=1; i<=r; i+=2)
		{
			if(num%i==0)
				sum += i + num/i ;
		}
	else //number is even
		for(int i=1; i<=r; i+=1)
		{
			if(num%i==0)
				sum += i + num/i ;
		}
	return sum;
}

Comments on line 4:

• The floor function to get any numbers after the decimal away (ie 12.9674 will be 12) you can remove it as we put our result in an integer so no numbers after decimal will be added. I just put it for illustration purposes.
• sqrt() function (at math.h) take one input of the type double so I did type casting for my integer num by adding (double) before it

The good news is that testing this function with the same main() written before, we got the best result you want to see

It takes less than one milli-Second

And using some advanced maths we can make the code much more shorter

Here is the last version I came with:

int SumOfDivisors(int num)
{
    int sum=0;
    for(int i=1; i*i<=num; i++)
		sum += (num%i)? 0 : ((i*i==num)? i : i+num/i);
    return sum;
}

same result

To understand the previous code well I have to show you some math equations.

Consider :

= 1 + p + + … +. (1)

Multiplying by p :

pσ() = p + + + … + . (2)

Subtracting (1) from (2):

pσ()−σ() = (p−1)σ() = − 1.

Hence

σ() = ( − 1)/(p − 1).

For example, σ()=(−1)/(3−1) = 242/2 = 121, and checking: 1 + 3 + 27 + 81 = 121.

Although no proof is supplied here, the usefulness of the function, σ(n), is its multiplicativity, which means that σ(a×b×…)=σ(a)×σ(b)×…, where a, b, …, are relatively prime.

Returning to example, we use the fact that σ(72) = σ(×). As and are relatively prime, we can separately work out σ() = − 1 = 15 and σ() = ( − 1)/2 = 13. Therefore, σ(72) = 15×13 = 195.

First change that line in our main()

ans = SumOfDivisors(158943609);

with this one:

for(int i=0; i<1000; i++)
		ans = SumOfDivisors(158943609);

and here are the results:
the 23 lines functions gives us:

and the 7 lines one gives us:

OOOOPS, it seems like my math may help in reducing the code lines but not the time it takes.