### SPyofgame's blog

By SPyofgame, history, 6 weeks ago, ,

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)

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

• -30

 » 6 weeks ago, # |   +2 Maybe your computer is slow
•  » » 6 weeks ago, # ^ |   -8 I thought that computer does not affect on compiling speed, thanks
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   -8 Are there any ways to calculate the real time of my code's compiling & calculating speed ?
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   +1 how many seconds — count of operations / $(10^8 * 1.5)$ (count of operations is your $O()$)
 » 6 weeks ago, # |   +1 ideone is slower too. Maybe, codeforces servers have a better cache, than you computer and ideone
•  » » 6 weeks ago, # ^ |   -8 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.
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 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$!
•  » » » » 6 weeks ago, # ^ |   0 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
•  » » » » 6 weeks ago, # ^ |   0 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) ~~
•  » » » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 linear sieve is not the best:)
•  » » » » » » 6 weeks ago, # ^ |   0 Bitwise Segment Sieve is much faster
•  » » » » » » » 6 weeks ago, # ^ |   0 $O(\frac{n}{64})$?
•  » » » » » » » » 6 weeks ago, # ^ |   0 Still O(n log log n) but the constant is much lower
•  » » » » » » » » » 6 weeks ago, # ^ |   0 linear sieve works in $O(n)$, yours in $O(n\log_{log_n}$