Thread: How can i make my programm faster?

  1. #1
    Registered User
    Join Date
    Jan 2014
    Location
    Athens, Greece, Greece
    Posts
    5

    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,'%');
    }

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,344
    I would focus on making your program readable first:
    • Indent your code properly.
    • 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?
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    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.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  4. #4
    Registered User
    Join Date
    Jan 2014
    Location
    Athens, Greece, Greece
    Posts
    5
    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. #5
    Registered User
    Join Date
    May 2009
    Posts
    4,067
    Quote Originally Posted by Patelakos View Post
    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
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  6. #6
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Quote Originally Posted by laserlight View Post
    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;
    }
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. extreamly slow IO, how to make it faster
    By baxy in forum C++ Programming
    Replies: 8
    Last Post: 12-01-2012, 10:37 PM
  2. Trying to make this run faster
    By wkohlani in forum C Programming
    Replies: 32
    Last Post: 06-27-2009, 11:42 PM
  3. Some help with make my programs faster
    By Sshakey6791 in forum C++ Programming
    Replies: 11
    Last Post: 12-11-2008, 01:41 PM
  4. does const make functions faster?
    By MathFan in forum C++ Programming
    Replies: 7
    Last Post: 04-25-2005, 09:03 AM
  5. Can i make my programm any better?
    By senegene in forum C Programming
    Replies: 3
    Last Post: 12-23-2002, 08:50 PM