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!