Running Time Difference!

[fishysun]

For the problem: https://www.spoj.com/problems/PRIME1/
I was basically toying with some data types until I noticed that the running times are pretty different …
Here is my 1st code which got accepted:

#include <bits/stdc++.h>
using namespace std;
int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	int t;
	cin >> t;
	long a, b;
	while(t--) {
		cin >> a >> b;
		for (register int j = a; j <= b; ++j) {
			bool flag = true;
			for (register int k = 2; k <= (int)sqrt(j); ++k) {
				if (!(j % k)) {
					flag = false;
					break;
				}
			}
			if (flag && (j != 1))
				cout << j << "\n";
		}
	}
	return(0);
}

The above code had a run time of only 0.99 seconds.

The next code also gets accepted, but I dunno why it is taking such a long time

#include <iostream>
#include<math.h>
using namespace std;
int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t;
	cin >> t;
	while (t--) {
		long n, m;
		cin >> n >> m;
		for ( register long i = n; i <= m; i++) {
			bool flag = true;
			for (register long j = 2; j <= (long)sqrt(i); j++) {
				if (!(i % j)) {
					flag = false;
					break;
				}
			}
			if (flag && (i != 1))
				cout << i << "\n";
		}
	}
}

It takes about 2.97 seconds !!

Can someone please explain this phenomena to me? Also one another question, the problem statement says that (1 <= m <= n <= 1000000000, n-m<=100000), that’s why I took long as a data type, but when I am looping , I chose the loop variable to an int, but the code still gets accepted. Wouldn’t that be a problem?( I am talking about the 1st code!)…

Thanks in advance!

[simes]

Which particular compiler are you using?

Have you checked that int and long are the size you think they are? I ran this on ideone with C++ 4.3.2, and it reported 4 and 8 respecitively. You could use asserts on spoj if you think spoj and ideone might be different.

cout << "int: " << sizeof(int) << "\n";
cout << "long: " << sizeof(long) << "\n";

[fishysun]

I use MinGW g++ 8.2.0…
Do you think it’s about long and int ?.. Or is there any other reason for the increased time?..Like the declarations of both the variable outside the test case function.

[devloping]

Looks like you changed your loop increments as well. i++ != ++i although the increment you could think as the same, the operators have different definitions example see operator overloading of prefix ++ vs postfix ++ here: https://docs.microsoft.com/en-us/cpp/cpp/increment-and-decrement-operator-overloading-cpp?view=vs-2019. Not sure that it really matters if returned by reference or not for primitive type though.

[bnnj]

I did some tests on your code and the types clearly change the running time.

I didn’t get as big a difference as you did, let’s say the fastest it ran was 5.3 secs, with only ints.
then, changing j to long increased it to about 6.3, k to long to 6.5, and both to 6.7 - surprisingly not by much, changing only one of them increases the time by 1 or 1.2 secs, and both by 1.4 secs.
Changing the cast of the sqrt return does the same thing as changing k, changing both is like changing one. I suppose because of the comparison, if only one is a long, the other is implicitly casted to long anyway.

I don’t know enough to explain such differences, but here’s some data that at least shows where it comes from.
I’m running it on manjaro kde with an i7 9750 and 16Go ram, testing a list of all numbers from 0 to 5000000 generated with a ruby script, redirected to a test_file, then time cat test_file | ./prime1