sieve.pyx

#!/usr/bin/env python

# Number to guess: How large of a prime can we find, 
# using a naive algorithm, in a second?

import sys
import itertools
import math
from libc.stdlib cimport malloc, free
cimport libc.stdio as stdio

cdef extern from "stdio.h":
    void *memset(void *str, int c, size_t n)

cdef primes_sieve2(char *a, int limit):
    #cdef np.ndarray a = np.ones(limit, dtype=np.bool_)
    cdef unsigned long sqrt_limit = <unsigned long>math.floor(math.sqrt(limit))
    memset(a, 1, limit)
    #a = [True] * limit                          # Initialize the primality list
    a[0] = a[1] = 0

    #for (i, isprime) in enumerate(a):
    cdef unsigned long i
    cdef unsigned long n
    cdef char isprime = 0
    for i from 0 <= i < sqrt_limit by 1:
        isprime = a[i]
        if isprime:
            #for n in xrange(i*i, limit, i):     # Mark factors non-prime
            for n from i*i <= n < limit by i:
                a[n] = 0
    return a

cdef c_f(int NUMBER):
    cdef char *sieve = <char *>malloc(NUMBER * sizeof(char))
    primes_sieve2(sieve, NUMBER)
    cdef int i
    #for i in xrange(NUMBER-1, 0, -1):
    for i from NUMBER-1 > i > 0 by 1:
        if sieve[i] == 1:
            stdio.printf("%d ", i)
            free(sieve)
            return

def f(NUMBER):
    return c_f(NUMBER)

if __name__ == '__main__':
    f(int(sys.argv[1]))