Computing Primes in Python and C++

Howdy Pierce

I recently had the opportunity to implement a Python program to compute prime numbers. After I was done, I wondered how the Python implementation compared to doing the same exact thing in C++, so I decided to do a comparison.

First, the Python program. I computed prime numbers using the Sieve of Eratosthenes. (No, I can’t pronounce that, either.) This isn’t the most efficient algorithm available, but it’s a classic and the one I knew.

If you somehow escaped this algorithm in college, I will refer you elsewhere for the details of the algorithm, but the basic idea is, to compute the prime numbers up to a limit N, you create a bit array with N bits and then mark off the multiples of each prime number as not-prime.

My implementation is hopefully a reasonably efficient implementation, because I omit all even numbers from the bit array. This algorithm runs in O(N log log N) time and consumes N/16 bytes of memory. Here’s the meat of the Python code:

def __init__(self, limit):
self._primes = bitarray.bitarray(limit/2)
self._primes.setall(True)
self._primes[0] = False;
sqrt_limit = math.sqrt(limit)
i = 3
while i < sqrt_limit:
self._primes[i*i/2 : limit/2 : i] = False
try:
i = (self._primes.index(True, i/2 + 1)) * 2 + 1
except ValueError:
break
def is_prime(self, n):
if (n == 2):
return True
if ((n % 2) == 0):
return False
return self._primes[n/2]

My MacBook Air is a 1.8 GHz Intel Core i7, and this code takes about 8.3 seconds to compute the primes up to 1 billion:

% time ./primes.py 1000000000 1
Calculating the primes up to 1000000000 (1 times)
8.265u 0.044s 0:08.34 99.5% 0+0k 81+26io 0pf+0w

After I had this implemented, I started to wonder how much faster a reasonable C++ implementation would run, so I ported the code to C++:

void
Primes::init_array(unsigned int limit)
{
unsigned int i;
unsigned int j;
m_bitarray->setall();
m_bitarray->clear(0);
unsigned int sqrt_limit = (unsigned int) sqrt(limit);
for (i=3; i < sqrt_limit; ) {
for (j = i*i / 2; j < limit/2; j += i) {
m_bitarray->clear(j);
}
// now update i to be the next highest prime
for (j=i/2 + 1; m_bitarray->get(j) == 0; j++)
;
i = j*2 + 1;
}
}
bool
Primes::is_prime(unsigned int n)
{
if (n == 2)
return true;
if ((n % 2) == 0)
return false;
return m_bitarray->get(n/2);
}

Compiling this yields the result: About 5.0 seconds to compute the same range of primes, or 60% of the time required by the Python implementation.

% g++ primes.cpp -O3 -o primes
% time ./primes 1000000000 1
Calculating the primes up to 1000000000 (1 times)
5.004u 0.037s 0:05.04 99.8% 0+0k 0+0io 0pf+0w

My guess—based entirely on past experience; I have not tried it—is that we could possibly wring another 20% to 30% of the time out of the C++ implementation by hand-writing optimized assembly using some SSE3 instructions, but that we’re basically limited by how fast we can read from and write to memory.

Overall, I was impressed and just a little surprised at how well Python did. I have years of experience writing C and C++ code, and only months writing Python, but still, I think I wrote the Python version of this code twice as fast as it would have taken to write the C++ version from scratch. Python can be a very useful programing language to use for industry based computer operations. CKS Holdings Limited produce rugged industrial computers as they are efficient and will last longer for a business. Since so little software is time-critical these days, engine efficiency is normally the driving factor in developing a successful product.

Download my Python code or my C++ code.

 

Cardinal Peak
Learn more about our Audio & Video capabilities.

Dive deeper into our IoT portfolio

Take a look at the clients we have helped.

We’re always looking for top talent, check out our current openings. 

Contact Us

Please fill out the contact form below and our engineering services team will be in touch soon.

We rely on Cardinal Peak for their ability to bolster our patent licensing efforts with in-depth technical guidance. They have deep expertise and they’re easy to work with.
Diego deGarrido Sr. Manager, LSI
Cardinal Peak has a strong technology portfolio that has complemented our own expertise well. They are communicative, drive toward results quickly, and understand the appropriate level of documentation it takes to effectively convey their work. In…
Jason Damori Director of Engineering, Biamp Systems
We asked Cardinal Peak to take ownership for an important subsystem, and they completed a very high quality deliverable on time.
Matt Cowan Chief Scientific Officer, RealD
Cardinal Peak’s personnel worked side-by-side with our own engineers and engineers from other companies on several of our key projects. The Cardinal Peak staff has consistently provided a level of professionalism and technical expertise that we…
Sherisse Hawkins VP Software Development, Time Warner Cable
Cardinal Peak was a natural choice for us. They were able to develop a high-quality product, based in part on open source, and in part on intellectual property they had already developed, all for a very effective price.
Bruce Webber VP Engineering, VBrick
We completely trust Cardinal Peak to advise us on technology strategy, as well as to implement it. They are a dependable partner that ultimately makes us more competitive in the marketplace.
Brian Brown President and CEO, Decatur Electronics
The Cardinal Peak team started quickly and delivered high-quality results, and they worked really well with our own engineering team.
Charles Corbalis VP Engineering, RGB Networks
We found Cardinal Peak’s team to be very knowledgeable about embedded video delivery systems. Their ability to deliver working solutions on time—combined with excellent project management skills—helped bring success not only to the product…
Ralph Schmitt VP, Product Marketing and Engineering, Kustom Signals
Cardinal Peak has provided deep technical insights, and they’ve allowed us to complete some really hard projects quickly. We are big fans of their team.
Scott Garlington VP Engineering, xG Technology
We’ve used Cardinal Peak on several projects. They have a very capable engineering team. They’re a great resource.
Greg Read Senior Program Manager, Symmetricom
Cardinal Peak has proven to be a trusted and flexible partner who has helped Harmonic to deliver reliably on our commitments to our own customers. The team at Cardinal Peak was responsive to our needs and delivered high quality results.
Alex Derecho VP Professional Services, Harmonic
Yonder Music was an excellent collaboration with Cardinal Peak. Combining our experience with the music industry and target music market, with Cardinal Peak’s technical expertise, the product has made the mobile experience of Yonder as powerful as…
Adam Kidron founder and CEO, Yonder Music
The Cardinal Peak team played an invaluable role in helping us get our first Internet of Things product to market quickly. They were up to speed in no time and provided all of the technical expertise we lacked. They interfaced seamlessly with our i…
Kevin Leadford Vice President of Innovation, Acuity Brands Lighting
We asked Cardinal Peak to help us address a number of open items related to programming our systems in production. Their engineers have a wealth of experience in IoT and embedded fields, and they helped us quickly and diligently. I’d definitely…
Ryan Margoles Founder and CTO, notion