a bit of optimization C++

[ichihgo]

This a C++ code which calculate the number with the greatest number of Divisors between a certain range 

 

Input >> Number of test cases >> A >> B ... Where ( A<B )

 

there's nothing wrong with the code it just exceed the time limit so I need a bit of optimization ... Any help ?

#include<iostream>#include<string>#include<vector>using namespace std;int main(){unsigned int num,start,en,countera=0,counterb=0,newa,cases;             //Start , en >> End , counter a (to check if the number of divisors more than the previous one (counter b) ) , Cases >> number of test casescin>>cases;                                                            //    newa >> new number which has more divisors unsigned int x[cases*2],y[cases*2],z[cases*2],v[cases*2];for(int k=0;k<cases;k++)                                                 // test cases loop{cin>>start>>en;                                                           // insert the rangenum=en;newa=en+1;for(int i=start;i<=en;i++)                                                // loop check the range itself{    countera=0;    counterb=0;    for(int j=num;j>0;j--)                                                // loop check the number of divisors    {        if(num%j==0)        countera++;    }    if(countera>=counterb && num<newa)                                  // condition if divisors is greater assign the greater number of divisors with the smallest value    {        newa=num;        counterb=countera;    }    num--;}    x[k]=newa;                                                                  // butting the result in the array     y[k]=counterb;    z[k]=start;    v[k]=en;}for(int i=0;i<cases;i++){cout<<"Between "<<z[i]<<" and "<<v[i]<<", "<<x[i]<<" has a maximum of "<<y[i]<<" divisors.";                    // loop for the outputif(i<cases-1)    cout<<endl;}    return 0;}

[Guest]

Having triple nested loops is going to result in terrible asymptotic time complexity. Find another way to do it.

[ichihgo]

Having triple nested loops is going to result in terrible asymptotic time complexity. Find another way to do it.

is this the only way ?

[Guest]

is this the only way ?

 

Can you add comments to your code explaining the contents or purpose of each variable?

[ichihgo]

Can you add comments to your code explaining the contents or purpose of each variable?

Yeah sure Give me a sec 

 

Will putting the loop as a function help ?

[Ciccioo]

Will putting the loop as a function help ?

it won't, because the problem is that the method you're using to find the number of divisors is slow (or at least, it's too slow for your specific purpose), so it doesn't matter how you translate it into code, the program runs slow as long as the algorithm is slow

 

the fastest way i know to find the number of divisors of a number is to find its prime factors, and then multiply all the exponents of the factors +1

44 = 2^2 * 11^1

(2 + 1) * (1 + 1) = 6 divisors (1, 2, 4, 11, 22, 44)

 

i think that there should be a way of doing this differently, in a "simpler" way based on the primes method, but my mind is starting to bend around this idea

[ichihgo]

it won't, because the problem is that the method you're using to find the number of divisors is slow (or at least, it's too slow for your specific purpose), so it doesn't matter how you translate it into code, the program runs slow as long as the algorithm is slow

 

the fastest way i know to find the number of divisors of a number is to find its prime factors, and then multiply all the exponents of the factors +1

44 = 2^2 * 11^1

(2 + 1) * (1 + 1) = 6 divisors (1, 2, 4, 11, 22, 44)

 

i think that there should be a way of doing this differently, in a "simpler" way based on the primes method, but my mind is starting to bend around this idea

 

Well sure that's way faster but could you please explain this part ? 

44 = 2^2 * 11^1

 

I did searched and I'm starting to understand how it works but if can explain it a bit , it would be great 

[Ciccioo]

Well sure that's way faster but could you please explain this part ? 

 

I did searched and I'm starting to understand how it works but if can explain it a bit , it would be great 

the idea is that you're scomposing your number into prime factors, which are the numbers that your number is made of.

if you think of what is a divisor, you realize that the divisors are just all the possible combinations between those prime factors, because a divisor must for definition have at least all the prime factors of the divided number.

multiplying the exponents+1 is just the formula to calculate the number of combinations in which the factors can be combine

[ichihgo]

the idea is that you're scomposing your number into prime factors, which are the numbers that your number is made of.

if you think of what is a divisor, you realize that the divisors are just all the possible combinations between those prime factors, because a divisor must for definition have at least all the prime factors of the divided number.

multiplying the exponents+1 is just the formula to calculate the number of combinations in which the factors can be combine

 

Okay now I got the concept about getting those 44 = 2^2 * 11^1     2 and 1 will it be by a loop ?

[Ciccioo]

Okay now I got the concept about getting those 44 = 2^2 * 11^1     2 and 1 will it be by a loop ?

well, to find those numbers you need to find the prime factors of your first number, so there's that

[alphabeta]

well, to find those numbers you need to find the prime factors of your first number, so there's that

 

searching time :lol:

[WanderingFool]

Well without getting too complex into optimization, lets just discuss the simplest ones.

 

You have a number X, and trying to see how many divisors/factors it has.

I am going to say X is the number, and D is a divisor.

 

X = D * N; //Since by definition D has to be multiplied by a whole number N is also a full number

 

So looking at this formula there is no point in finding D and then later finding N....but lets limit the case by saying only finding D's so that D < N.  So now you are pairing up each D with an N.  So the count should be 2 times the amount of D's you find.  The exception would be when D * D = X, then you can add one.  So with that math said a loop to count the factors could look something like this.

int targetNum = 123456;int numFactors = 1; //1 will always be a factor so start at 2double sqrtOfTarget = sqrt(targetNum);for(d = 2; d < sqrtOfTarget; d++) { //Notice that I an only going to the sqrt...because anything				//beyond sqrtOfTarget will now mean targetNum = d * n; where d > n...so d would have been counted already when d and n were switched	if(targetNum%d == 0)		numFactors++;}numFactors = numFactors * 2; //To compensate for the matching n's//Now we have a problem when it is a sqrt, ie numbers like 9 as 3 would not have been counted.//Luckily we can do a single check of d to determine thatif(d*d == targetNum) //Since d is now equal to the number closest int above = sqrtofTarget	numFactors++;//And presto, numFactors should be the number correct with doing less than half the amount of compares (if I am correct)//So on 100,000,000, instead of doing 100 million compares, you are only doing 10 thousand

[Midnight]

If the range of the input is known. Then, I would pre-compute a sieve and factor each number in the range for each test case.

[ichihgo]

 

--

 first of thanks 

 

I did applied you solution but the output is a little fuzzy what's wrong ?

 

Edit : It worked thanks

 

the working one

#include<iostream>#include<iomanip>#include<cmath>using namespace std;int checkdiv(int x){double SqrtOfnumber;SqrtOfnumber=sqrt(x);int counter=0,i;for(i=1;i<SqrtOfnumber;i++){if(x%i==0)counter++;}counter=counter*2;if(i*i == x)counter++;return counter;}int main(){unsigned int start,en,countera,counterb,newa,cases,i,k;cin>>cases;unsigned int x[cases*2],y[cases*2],z[cases*2],v[cases*2];for(k=0;k<cases;k++){countera=0;counterb=0;cin>>start>>en;newa=en+1;for(i=en;i>=start;i--){countera=0;countera=checkdiv(i);if(countera>=counterb && i<newa){newa=i;counterb=countera;}}x[k]=newa;y[k]=counterb;z[k]=start;v[k]=en;}for(i=0;i<cases;i++){cout<<"Between "<<z[i]<<" and "<<v[i]<<", "<<x[i]<<" has a maximum of "<<y[i]<<" divisors.";if(i<cases-1)cout<<endl;}return 0;}