CODEWITHSUNDEEP
pythonalgorithmnumberstime-complexityprimes
Soumyajit Ray
Soumyajit Ray

Reputation: 35

Need Help! Count Primes using python

Count the number of prime numbers less than a non-negative number, n. I have created the following code but the complexity is too high. I would really be grateful if some one give me a better resolution.

import math
class Solution(object):
    def countPrimes(self, n):
        PrimeCount=0
        primelist=[]
        for i in range(2,n):
            if self.primeCheck1(i,primelist)==True:
                primelist.append(i)       #try2 with new logic
                PrimeCount=PrimeCount+1

        return PrimeCount



    def primeCheck1(self,n,primelist):
        flag=False
        if n==2:
            return True
        elif n==3:
            return True
        sqroot=int(math.sqrt(n))

        for j in range(0,sqroot):
            if n%primelist[j]==0:
                flag=True
                break

        if flag!=True:
            return True
        else:
            return False

Upvotes: 1

Views: 5356

Answers (5)

Mastan Abdulkhaligli
Mastan Abdulkhaligli

Reputation: 1

def count_primes(prime):

    check=2
    main_res=0

    while check <= prime:
        result=0
        control=1
        while control <= check: 
            if check%control==0:
                result+=1
                control+=1
            else:
                control+=1
        if result==2:
            main_res+=1


        check+=1

    return main_res


# Test for COUNT PRIME
#print(count_primes(100))

Upvotes: 0

Shaon shaonty
Shaon shaonty

Reputation: 1415

You can use bitwise sieve algorithm.

SIZE = 1000000
LIMIT=int(math.sqrt(SIZE)+1)

prime = []

def sieve():
    for i in range(SIZE/32):
        prime[i]=0xffff
        prime[0]&=~(1<<(1%32))

    for i in range(LIMIT+1):
        if(prime[i/32]&(1<<(i%32))):
            for j in range(2*i, SIZE, j=j+i):
                prime[j/32]&=~(1<<(j%32))

def isPrime(n):
        return prime[n/32]&(1<<(n%32))

Upvotes: 0

cdlane
cdlane

Reputation: 41872

A rework of your code that speeds it up 3X counting the number of primes less than a million:

class Solution(object):
    def countPrimes(self, n):
        primelist = []

        for i in range(2, n):
            if self.primeCheck(i, primelist):
                primelist.append(i)

        return len(primelist)

    def primeCheck(self, n, primes):

        if n < 2:
            return False

        if n % 2 == 0:  # 2 is the only even prime
            return n == 2

        for prime in primes:

            if prime * prime > n:  # easier to square many than sqroot one
                return True

            if n % prime == 0:  # divisible by a prime, not a prime
                return False

        return True

solution = Solution()

print(solution.countPrimes(1000000))

This includes some of the tricks @rossum pointed out to you.

However, we can do better. Here's a reimplementation using @ClockSlave's prime sieve code that's 22 times faster than your original when counting the number of primes less than a million:

class Solution(object):

    def __init__(self):
        self.sieve = None

    def countPrimes(self, n):

        self.sieve = [True] * n

        if n > 0:
            self.sieve[0] = False
            if n > 1:
                self.sieve[1] = False

        def mark_sieve(prime):
            for index in range(prime + prime, n, prime):
                self.sieve[index] = False

        for number in range(2, int(n ** 0.5) + 1):
            if self.sieve[number]:
                mark_sieve(number)

        return sum(self.sieve)

solution = Solution()

print(solution.countPrimes(1000000))

The win here is eliminating all those expensive divisions.

Upvotes: 1

rossum
rossum

Reputation: 15685

I like the way you build a list of primes and use that list to detect larger primes. You are right that your code is more complex than it needs to be, specifically your flag variable is not needed.

You have missed a few tricks in your primeCheck1() method as well that can speed things up. Since my Python is non-existent, this is in Python-like pseudocode. I assume you will be able to convert it.

def primeCheck1(self, n, primelist):

  # Handle even numbers.
  if n % 2 == 0:
        # The only even prime is 2.
        return (n == 2)

  # Handle multiples of 3.
  if n % 3 == 0:
        return (n == 3)

  # Handle remaining numbers.
  sqroot = int(math.sqrt(n))

  for j in range(0, sqroot):
    if n % primelist[j] == 0:
      return False  # Not a prime number.

  # If we get this far then the number is prime.
  return True

end primeCheck1

On a minor point, you have a habit of not spacing out your code: a==b instead of a == b. Using spaces as separators makes code easier to read.

Upvotes: 2

whackamadoodle3000
whackamadoodle3000

Reputation: 6748

First install the sympy package with pip install sympy. Then try this:

import sympy
PrimeCount=0
n=int(input("Number?"))
for elem in range(n):
   if sympy.isPrime(elem):
      PrimeCount+=1
print(PrimeCount)

Upvotes: 0

Related Questions