# Thread: How can i make my programm faster?

1. ## How can i make my programm faster?

Hey guys i am pretty new to C and i created this programm to determine if a number is a Smith number. The only problem is that for big numbers it runs really slow.It takes about 10 minutes.Any idea how to improve it?Thank you in advance

Here is the code :
Code:
```#include<stdio.h>

int main(){

int sum,sum1,j,j1,save,current,counter,n,many=0;
float percent;
for(counter=200000000;counter<=200010000;counter++)
{
sum=0;
sum1=0;
j=2;

current=counter;
save=current;

while(save>=10)
{ sum=sum+save%10;
save=save/10;
}

sum=sum+save;

save=current;

while(save%j==0)
{ sum1=sum1+j;
save=save/j;
}

j++;
while(save!=1)
{

while(save%j==0)
{
save=save/j;
j1=j;

while(j1>=10)
{
sum1=sum1+j1%10;
j1=j1/10;

}

sum1=sum1+j1;
}
j=j+2;
}
n=j-2;
if(sum==sum1 && current!=n)	{

printf("The number %d is Smith \n",current);
many=many+1;
}
}
percent=1.0*many/100;

printf("%.4f%c  Smith numbers found",percent,'%');
}```

• Instead of sum and sum1, [b]digit_sum[b] and prime_factors_digit_sum would be more descriptive.
• Write two functions: one function takes an integer and returns the sum of its digits; the other function takes an integer and returns the sum of the digits of its prime factors.

After that, check: does your program correctly finds Smith numbers? What happens if the number's prime factorisation contains repeated primes?

3. I suggest revisiting your basic algorithm.

For example, your loop is finding prime factors every time through the loop, which will slow things down considerably for large values. Instead, try to find a suitable set of prime factors first (say, all the primes that do not exceed the square root of the maximum value you're checking) and use that on every iteration of the loop.

No matter what you do, however, the approach will be slower for large values than for small ones.

4. Well to be honest i don't really know hot to create a fuction.I try to work with the things that i got but i may give it a shot.

5. Originally Posted by Patelakos
Well to be honest i don't really know hot to create a fuction.I try to work with the things that i got but i may give it a shot.
Functions in C - Cprogramming.com

6. Originally Posted by laserlight
After that, check: does your program correctly finds Smith numbers? What happens if the number's prime factorisation contains repeated primes?
The algorithm seems to be correct. In particular, it does test for repeated factors. Here's a rewrite with no change in the algorithm. Hopefully it's a little easier to read.
Code:
```#include <stdio.h>

#define START 4
#define STOP  1100

int main() {
int n, i, j, k, count = 0;

for (n = START; n <= STOP; n++)
{
int sum_digs = 0, sum_facts = 0;

for (i = n; i > 0; i /= 10)
sum_digs += i % 10;

sum_facts = 0;
for (i = n; i % 2 == 0; i /= 2)
sum_facts += 2;

for (j = 3; i != 1; j += 2)
for ( ; i % j == 0; i /= j)
for (k = j; k > 0; k /= 10)
sum_facts += k % 10;

// The second test ensures n is not prime.
if (sum_digs == sum_facts && n != j - 2) {
printf("%d ", n);
++count;
}
}

printf("\n%.2f%% of the numbers between %d and %d are Smith numbers.",
(double)count / (STOP - START + 1) * 100.0, START, STOP);

return 0;
}```