Improve the speed of my program

[NOSgraf]

Write your question here.
I'm new to c++ and here i have a simple program which works but the site of our university does not approve of it because it works more than > 1.000 sec. So i want someone if possible to give me tips on how to improve the speed of my program

#include <iostream>
using namespace std;
int main()
{
int N;
cin >> N;
while (N--) {
int L, R, count = 0, a = 4, b = 7;
cin >> L >> R;
for (int i = L; i <= R; i++) {
if (i % a == 0 || i % b == 0) {
count++;
}
}
cout << count << endl;
}
return 0;
}

[keskiverto]

You could calculate from L and R the count of times an even multiple occurs. Without a loop.
Something almost (but not quite) like:

lo = L / a; // lo can be off-by-one. Why?
hi = R / a;
count += 1 + hi - lo;

[NOSgraf]

Well i don't really get what you mean but in case i think i should tell you that i want my program to print out how many numbers(between L and R including them) exist which can be divided by 4 or 7. For example:
Input
5
4 7
1 10
17 19
3 33
1234 4321

Output
2
3
0
11
1103
By the way N represents the number of test cases

[coder777]

You can use the formula keskiverto provided for both: 4 and 7. Thus you don't need a loop to evaluate the count of the divider.

[lastchance]

hi = R / a;    // due to INTEGER DIVISION, gives whole number multiples less than or equal to R
               // now you need to remove the number of multiples that are STRICTLY less than L ... or, equivalently, less than or equal to L - 1 ...
lo = ( L - 1 ) / a;    
count  +=  hi - lo;  

This gives the number that are divisible by a. Obviously, you could simplify this to a single statement.

Do the same for the number that are divisible by b.

Now you have double-counted those that are divisible by BOTH a and b, so SUBTRACT the number divisible by a*b (=28, here).


In principle, you can get count in a one-line calculation, without a loop.


This will work provided:
L and R are both positive (because rounding from integer division occurs toward 0)
a and b are coprime (so that a*b is the smallest number divisible by both)
Both conditions seem to be met in your assignment.

[keskiverto]

1234/4 = 308
4321/4 = 1080
Are there 773 numbers in that range that are multiples of 4?

1234/7 = 176
4321/7 = 617
Are there 442 numbers in that range that are multiples of 7?

Oh, we count some numbers (the 4*7*k) twice.
1234/28 = 44
4321/28 = 154
Are there 111 numbers in that range that are multiples of 28?

773+442-111 = 1104 (hmm, I might have an error somewhere.)

[lastchance]

count = R / a - ( L - 1 ) / a + R / b - ( L - 1 ) / b - ( R / ( a * b ) - ( L - 1 ) / ( a * b ) );

[NOSgraf]

Thanks it worked , it took me some time to understand it but now it seems so simple thank you very much .