SPyofgame's blog

By SPyofgame, history, 6 weeks ago, In English,

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

 
 
 
 
  • Vote: I like it
  • -30
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Maybe your computer is slow

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

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

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it -8 Vote: I do not like it

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

    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

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

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    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   Vote: I like it 0 Vote: I do not like it

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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   Vote: I like it 0 Vote: I do not like it

          linear sieve is not the best:)

          • »
            »
            »
            »
            »
            »
            6 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Bitwise Segment Sieve is much faster

            • »
              »
              »
              »
              »
              »
              »
              6 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

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

              • »
                »
                »
                »
                »
                »
                »
                »
                6 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

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