Like Tree2Likes
  • 1 Post By Salem
  • 1 Post By tabstop

Dividers

This is a discussion on Dividers within the C Programming forums, part of the General Programming Boards category; I need to solve this problem. Could someone help me? In the interval from 1 to the given number N, ...

  1. #1
    Registered User
    Join Date
    Jun 2011
    Posts
    4

    Dividers

    I need to solve this problem. Could someone help me?

    In the interval from 1 to the given number N, your task is to find the number which has the most divisors. In case there is more than one solution, find the smallest one.

    INPUT:
    From the standard input read the number N ( 0 < N < 2^31 ).

    OUTPUT:
    The standard output should contain two numbers (one in each line). The first line should contain the (smallest) number which has the most divisors, and the second line should contain the number of divisors.

    Code:
    this is my version, but its not absolutely correct: 
    
    #include <stdio.h>
    #include <math.h>
    
    int main(){
    
    int n,i,br,max,p,k;
    
    scanf("%d",&n);
    max=0;
    for(i=1;i<=n;i++){
    br=0;
    	for(k=1;k<=sqrt(i);k++){
    		if (i%k==0) br++;
    		if (br>max) {
    			max=br; p=i;
    			}
    		}
    	}	
    printf("%d\n%d\n",p,br);
    
    return 0;
    }

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,333
    Step 1 is learn how to indent code. It helps everyone (including you) to figure out what is going on.
    Code:
    #include <stdio.h>
    #include <math.h>
    
    int main()
    {
        int n, i, br, max, p, k;
    
        scanf("%d", &n);
        max = 0;
    
        for (i = 1; i <= n; i++) {
            br = 0;
            for (k = 1; k <= sqrt(i); k++) {
                if (i % k == 0)
                    br++;
                if (br > max) {
                    max = br;
                    p = i;
                }
            }
        }
    
        printf("%d\n%d\n", p, br);
    
        return 0;
    }
    SourceForge.net: Indentation - cpwiki

    > int n, i, br, max, p, k;
    Next, give all your variables some meaningful names, not cryptic 1 or 2 letters.

    For example,
    int currentBestNumber, currentBestNumDivisors;
    quzah likes this.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    Apr 2006
    Posts
    2,010
    Step 3 is to describe what your program is doing wrong.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  4. #4
    Registered User
    Join Date
    Jun 2011
    Posts
    4
    program is doing fine, but its not absolutely correct

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by Dule View Post
    program is doing fine, but its not absolutely correct
    Well, if it was doing fine, then it would be correct, wouldn't it? You need to identify what is not correct about what you have.

    (Upon a second reading, please tell me the answer isn't "I was printing br when I was supposed to be printing max.")
    Last edited by tabstop; 06-08-2011 at 03:59 PM.

  6. #6
    Registered User
    Join Date
    Jun 2011
    Posts
    4
    program needs to be faster... and there is no part in code that ask what if there are two with same numbers of dividers could you please write your version?

  7. #7
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by Dule View Post
    program needs to be faster...
    Upgrade some hardware, then. [If you actually want fancy, then you need to do some prime factorization (not just any old factorization) and use the (n1+1)(n2+1)(n3+1)...(nk+1) formula, where the n's are the exponents on the prime factors.] EDIT: Actually there is one really easy change you can make that will probably speed things up a lot, and that's moving the calculation of the square root outside of your loop, since it doesn't change. You can also move the checking against max outside of the inner loop as well.
    Quote Originally Posted by Dule View Post
    and there is no part in code that ask what if there are two with same numbers of dividers
    According to the specifications you posted, any attempt to do so would be incorrect, so I am curious as to why you would want such a thing.
    Last edited by tabstop; 06-08-2011 at 04:19 PM.
    Salem likes this.

  8. #8
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,333
    Mmmm, faster you say - how about turning on the optimiser?
    Code:
    $ gcc baz.c -lm
    $ time ./a.out 
    1000000
    720720
    25
    
    real	0m35.909s
    user	0m31.498s
    sys	0m0.036s
    
    # Optimise it
    $ gcc -O2 baz.c -lm
    $ time ./a.out 
    1000000
    720720
    25
    
    real	0m21.969s
    user	0m19.625s
    sys	0m0.020s
    
    # Now with tabstop's suggestions
    $ gcc -O2 baz.c -lm
    $ time ./a.out 
    1000000
    720720
    25
    
    real	0m17.691s
    user	0m15.297s
    sys	0m0.028s
    $
    Twice as fast is very achievable with some simple changes.

    But if you want it to be really fast, you need a better algorithm (assuming one exists).
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,261
    I would at least move the square root out of the loop, but better yet, you can eliminate it entirely by keeping it in a variable say 'rootN' and only increment it when rootN*rootN is less than N.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21