CODEWITHSUNDEEP
pythonalgorithmtime-complexityprimality-test
Adi219
Adi219

Reputation: 4814

What's the Time Complexity of my Primality Test?

I have a basic understanding of how to calculate Time Complexities, but I'm not sure how to calculate it in this case due to the random nature of primes.

A quick explanation --> Essentially, I'm keeping a running count of the remainders so that I know when the next prime is.

My code:

import math

n = int(input("Enter the number:\t"))

primeList = []
checkList = []

number = 3
isPrime = True
while number <= math.sqrt(n) and isPrime:

    isChanged = False
    for i, checkNum in enumerate(checkList):
        if checkNum == 1:
            isChanged = True
            checkList[i] = primeList[i]
        else:
            checkList[i] = checkNum - 1

    if not isChanged:

        primeList.append(number)
        checkList.append(number)

        if n % number == 0:
            isPrime = False

    number += 2

if isPrime:
    print("Prime")
else:
    print("Not Prime")

Upvotes: 2

Views: 604

Answers (1)

John Coleman
John Coleman

Reputation: 52008

Your algorithm seems to be O(n/log(n))

There are sqrt(n) passes through the outer loop. The inner loop is bounded by the number of primes which are less than sqrt(n). By the Prime Number Theorem this is asymptotically given by sqrt(n)/log(sqrt(n)). By the laws of logarithms this is equivalent to sqrt(n)/(0.5*log(n)) = 2*sqrt(n)/log(n). The overall complexity is thus

O(sqrt(n)*2*sqrt(n)/log(n)) = O(2*n/log(n)) = O(n/log(n))

Needless to say, this isn't a very efficient way to check if n is prime. It is asymptotically little better than the O(n) naive check for divisibility by all numbers less than n.

Upvotes: 4

Related Questions