I use Visual Studio Code and run Linear Sieve (using Smallest Prime Factor). When I compile in vscode, the limit under 1 second is ~27e6 = 27.000.000. But when I use Custom Test in Codeforces. It can run up to ~120e6 = 120.000.000 in 888ms :O (I was shock when see that, it is very fast)

I have searched on google but see no answer ;-;

My code right here

```
#include <iostream>
#include <vector>
using namespace std;
typedef vector<int> vi;
typedef vector<bool> vb;
vi prm;
vi spf;
void sieve(int n) // up_to 27e6 = 27.000.000
{
prm.clear();
if (n < 2) return ; prm.push_back(2);
spf.assign(n + 1, 2);
spf[0] = spf[1] = 0;
for (int i = 3; i <= n; i += 2) {
if (spf[i] == 2)
prm.push_back (spf[i] = i);
for (int j = 0; j < prm.size() && prm[j] <= spf[i] && i * prm[j] <= n; ++j)
spf[i * prm[j]] = prm[j];
}
}
bool isPrime(int x) { return spf[x] == x; }
int main()
{
int n;
cin >> n;
sieve(n);
int p = prm.size();
cout << p << endl;
return 0;
}
```

Sorry for my bad English and if I have mistaken something please tell me. ;-;

Thanks for reading. Have a good coding day guys <3

Maybe your computer is slow

I thought that computer does not affect on compiling speed, thanks

Are there any ways to calculate the real time of my code's compiling & calculating speed ?

how many seconds — count of operations / $$$(10^8 * 1.5)$$$ (count of operations is your $$$O()$$$)

ideone is slower too. Maybe, codeforces servers have a better cache, than you computer and ideone

Oh, ok. So how should I evalutate my code ? Are there any website to do that ? Because sometimes I need to know the real limitation of variable for my algorithms. I am afraid of wrong evalutate complexity in the contest.

pure math & experience; for example: given array consisting of $$$n$$$ elements. you need to find number of pairs $$$(i, j)$$$ such that $$$gcd(a_i, a_j)\leq 15$$$. $$$n\leq 1000$$$, $$$a_i\leq 10^9$$$. you can solve this problem in quadratic time. so your code will work in $$$O(n^2)$$$ time. (so time = $$$1000^2$$$ / $$$(10^8*1.5)$$$ seconds which is $$$\approx$$$ $$$0.007$$$ in worst case). hope explanation was clear $$$\ddot\smile$$$!

I have just learn about sieve.

Atkin sieve has time complexity of O(n / log log n)

Eratosthenes sieve has time complexity of O(n * log log n)

But that does not mean Eratosthenes sieve Slower than Atkin. The implementations matter and I need to calculate the limitation input under 1 second. I found that on my computer. Atkin sieve's input limit is smaller Eratosthenes sieve's

I want to calculate the real limit just to compare the sieves (Trial Division Sieve, Sundaram Sieve, Eratosthenes Sieve, Atkin Sieve, Divisor Sieve, Euler Totient Sieve) ~~

linear sieve is not the best:)

Bitwise Segment Sieve is much faster

$$$O(\frac{n}{64})$$$?

Still O(n log log n) but the constant is much lower

linear sieve works in $$$O(n)$$$, yours in $$$O(n\log_{log_n}$$$