Thread: Erroneous answer in algorithm problem

Hi All,

I am writing a program to find the smallest positive integer that has n or more divisors. My program gives me correct answer for input values upto 4 but it produces erroneous answers for input values above 4. For example, it gives 10 as integer having 5 divisors).

Please point out errors or modifications. Below is the program:

Code:

/*program to find smallest positive integer that has n or more divisors excluding itself*/
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int main()
{
int n,i,posinteger=1,count=0,halfposinteger=0;
printf("enter the number of divisors");
scanf("%d",&n);
if(n<=4)
{
        for(i=1;i<=n;i++)
        {
            posinteger*=i;
        }
}
else
{
    posinteger=8;
    while(count!=n)
    {
        posinteger+=1;
        halfposinteger=floor(posinteger/2);
        for(i=1;i<=halfposinteger;i++)
        {
             if(posinteger%i==0)
             {
                    count+=1;            
             }
        }
    }   
}
printf("the smallest positive integer with %d divisors is %d",n,posinteger);
system("pause");
return 0;
}

Hi Stahta,

Resetting count solves my problem. Thank you.

Originally Posted by stahta01

Every time you test a new number you have to reset count back to zero.

After major re-write of your code I got this output.

FYI: the number 1 has no whole number divisors when 1 is not counted.

Code:

the smallest positive integer with 1 divisors is 2
the smallest positive integer with 2 divisors is 4
the smallest positive integer with 3 divisors is 6
the smallest positive integer with 4 divisors is 12
the smallest positive integer with 5 divisors is 12
the smallest positive integer with 6 divisors is 24
the smallest positive integer with 7 divisors is 24
the smallest positive integer with 8 divisors is 36
the smallest positive integer with 9 divisors is 48

Test framework I used; I have no plans to post my smallestWithDifferentDivisors function.

Code:

/*program to find smallest positive integer that has n or more different divisors excluding itself*/
#include<stdio.h>
#include<stdlib.h>

int smallestWithDifferentDivisors(unsigned int  minCount);

int main() {
    int i=0;
    int result=0;

    for (i=1; i<10; i++) {
        result = smallestWithDifferentDivisors(i);
        printf("the smallest positive integer with %d divisors is %d\n",i,result);
    }
    return 0;
}

Tim S.

Hi Stahta,

My program gives the following results to me:

the smallest positive integer with 1 distinct divisors is 1
the smallest positive integer with 2 distinct divisors is 2
the smallest positive integer with 3 distinct divisors is 6
the smallest positive integer with 4 distinct divisors is 12
the smallest positive integer with 5 distinct divisors is 12
the smallest positive integer with 6 distinct divisors is 24
the smallest positive integer with 7 distinct divisors is 24
the smallest positive integer with 8 distinct divisors is 36
the smallest positive integer with 9 distinct divisors is 48


Below is my modified code:

Code:

/*program to find smallest positive integer that has n or more distinct divisors excluding itself*/
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int smallestWithDistinctDivisors(unsigned int  minCount);
int main()
{
    int i=0;
    int result=0;
 
    for (i=1; i<10; i++)
    {
        result = smallestWithDistinctDivisors(i);
        printf("the smallest positive integer with %d distinct divisors is %d\n",i,result);
    }
    system("pause");
    return 0;
}

int smallestWithDistinctDivisors(unsigned int  minCount)
{
int n,i,posinteger=1,count=0,halfposinteger=0;
if(minCount<4)
{
        for(i=1;i<=minCount;i++)
        {
            posinteger*=i;
        }
}
else
{
    posinteger=8;
    while(count<minCount)
    {
        count=1;           
        posinteger+=1;
        halfposinteger=floor(posinteger/2);
        for(i=2;i<=halfposinteger;i++)
        {
             if(posinteger%i==0)
             {
                    count+=1;            
             }
        }
    }   
}
return posinteger;
}

Thanks for your help.