# What is the complexity of this prime trial division algorithms?

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.

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