1
$\begingroup$

I have two algorithms. What are their time complexities? The first algorithm checks the modulo of all odd integers from $3,5,...\sqrt{n}$. The second algorithm generates a list of prime from $2,3...,\sqrt{n}$ and divides the input, $Num$ by these primes.

Algorithm 1 needs $\sqrt{Num}/2$ modulo divisions in the worst case, and Algorithm 2 needs just $\sqrt{Num}/\log{n}$ modulo divisions. Algorithm 1:

        bool IsPrime(BigInteger Num)
        {
            if (Num < 2) return false;
            else if (Num < 4) return true;
            else if (Num % 2 == 0) return false;
            else for (BigInteger u = 3; u * u <= Num; u += 2)
                    if (Num % u == 0) return false;
            return true;
        }

Algorithm 2:

        bool IsPrimeBetter(BigInteger Num)
        {
            ulong arrayLe = (ulong)Isqrt((long)Num);//Sqrt of Num
            if (Num < 2) return false;
            else if (Num < 4) return true;
            else foreach (var prime in new Atkin(arrayLe))//Atkin sieve which generate list of primes from 2 to √Num
                    if (Num % prime == 0) return false;
            return true;
        }

I don't really know how to check complexity of them.

$\endgroup$
  • $\begingroup$ Hello and welcome to cs.stackexchange! Your second algorithm does not look like complete, readable pseudo-code. What is Atkin? What is arrayLe? $\endgroup$ – BearAqua Apr 28 at 17:13
  • $\begingroup$ Hi, post edited. Atkin - atkin sieve to generate primes. arrayLe - sqrt of Num $\endgroup$ – Papaj Chan Apr 28 at 17:19
1
$\begingroup$

The first one is easy: Figure out how often you will iterate through the loop in the worst case.

The second one is harder: Again, you need to figure out how often you will iterate through the loop. However, you also need to figure out how long it takes to calculate the list of primes, and how long it takes to enumerate all those primes.

In practice, you would likely check many numbers for primality, so you wouldn't create a complete new sieve every time, but keep the previous sieve, and extend it when checking a larger prime number.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.