Computing primes, in Python and C0

This page shows a simple program in Python is rewritten in C0. The original Python source, sieve2.py is due to David Kosbie.

We begin with the fourth function defined: what is a prime number?

def isPrime(n):
    if (n < 2): return False
    # deal with evens first (to cut time in half)
    if (n == 2): return True
    if (n % 2 == 0): return False
    # then only check odds up to the square root
    for factor in range(3, 1+int(round(n**0.5)), 2):
        if (n % factor == 0):
            return False
    return True

The first difference we have to account for is that functions are typed, which means we have to specify that isPrime takes an integer argument and returns a boolean (either true or false)

bool isPrime(int n)
{
  ...
}

Rather than relying on indendation, the body of the function is enclosed in curly braces {...}. You will see many of these when writing code in C0.

Prime numbers are integers greater or equal to 2, so just as in the Python code we first check whether it is a valid candidate and return false if it isn't. The constant false is all in lowercase, and this matters; False would be flagged as an undeclared identifier.

bool isPrime(int n)
{
  if (n < 2) return false;
  ...
}

In C0, there is no colon (:) after the condition, and the return statement is followed by semicolon (;). All simple statements in C0 are followed by semicolons, but not compound statements like conditionals. Therefore we know that the semicolon "belongs to" the return statement, rather than the condition.

The next two lines in the Python code are an optimization, which we can faithfully reproduce. The constant true is also in lowercase. The modulus and comparison operators are like in Python, except that C0 enforces that the two sides are expressions of the same type.

bool isPrime(int n)
{
  if (n < 2) return false;
  if (n == 2) return true;
  if (n % 2 == 0) return false;
  ..
}

Let's look again at the remainder of the Python function.

  for factor in range(3, 1+int(round(n**0.5)), 2):