Source for Prime Number Checking

Back in November, I posted about how C was tangibly faster than Python.

Today, I got a comment (don’t look for it, it’s on the old site) asking for the source code.

So here’s the original, in C:

#include <stdio.h>
#define VERSION “1.0″

//Runs a prime check on a given integer
//Returns 1 if prime, 0 if composite
int isPrime(int prime)
{
int count=2;

//Special cases:
if(prime==1)
{
return 0;
}
else if(prime==2)
{
return 1;
}
else
{
while(prime%count != 0 && count*count <= prime)
{
count++;
}
return (prime%count==0)?0:1;
}
}

//Print version information
void printVersion()
{
printf(”Primality checker version %s\n”, VERSION);
printf(”Compiled on %s %s\n”, __DATE__, __TIME__);
}

int main()
{
int i=1;
const int max_prime=2500;

printVersion();

for(i=1; i<max_prime; i++)
{
if(isPrime(i))
{
printf(”%d is prime\n”, i);
}
else
{
printf(”%d is not prime\n”, i);
}
}
return 0;
}

and here’s my Python port (and it doesn’t even have printVersion())…

def isPrime(prime):
    ”’Runs a prime check on a given integer
    Returns 1 if prime, 0 if composite”’
    count=2;
    if prime==1:
        return 0;
    elif prime==2:
        return 1;
    else:
        while prime%count != 0 and count*count <= prime:
        count += 1
        if prime % count == 0:
            return 0
        else:
            return 1
max_prime=2500
for i in range(1, max_prime + 1):
    if isPrime(i):
        print “%d is prime\n” %i
    else:
        print “%d is not prime\n” %i

However, I’d also like to point out that the C version is 55 lines long, and the Python one is only 21. Yes, that’s counting braces. Yes, that’s counting printVersion(), and yes, that’s counting stuff like include <stdio.h>, and int main(). But it’s still impressive.

(PS: If somebody knows of  a better way of pasting code, let me know).

Share/Save/Bookmark

Category: Uncategorized
You can leave a comment or trackback from your own site.

6 Responses to “Source for Prime Number Checking”

  1. Arthur says:
    February 7, 2009 at 11:32 AM

    You could paste the code in pastebin (http://pastebin.com/) and link to it or use http://tohtml.com/ to generate highlighted html code and include it here.

    Reply
  2. Steve Pinkham says:
    February 7, 2009 at 11:52 AM

    http://pastie.org/ for pasting code

    Reply
  3. Steve Pinkham says:
    February 7, 2009 at 11:54 AM

    http://pastie.org/help/ for directions on pasting code with different syntax highlighting for each section.

    Reply
  4. Andrew Dalke says:
    February 7, 2009 at 2:18 PM

    Were I to need performance in Python I would use gmpy. “import gmpy; gmpy.is_prime(n)”.

    You would greatly improve the performance of both codes by using the sieve of Eratosthenes, which is harder to implement in C because it requires a growing list if you have arbitrary sized values. If you’re restricting yourself to small values, you can pre-code the possible primes (smallprimes=(2,3,5,7,11,13,17, ..). for p in smallprimes: if n%p==0: return 0; …. return 1)

    If you have a large but restricted set of values,you can use a deterministic version of the Miller-Rabin test. Jaeschke showed that for under 2**32 you only need 3 tests. This should be quite fast to test in C, but the modulo exponentiation isn’t built-in to C like it is in Python. I’ve never done any timings though – I use gmpy.

    Reply
  5. Chaoticmass says:
    February 7, 2009 at 2:34 PM

    FYI, in either language, each program probably spends more time just printing to the terminal than anything else. It is best to omit the printing to the terminal part or you may inadvertantly end up benchmarking the language’s output implementation and not what you intended to really test. At least have the programs only print when a prime is found and skip printing every non-prime found.

    But yes, while I like both C and Python, there is no question that C is balls out faster.

    Reply
  6. Andrew Dalke says:
    February 7, 2009 at 3:57 PM

    Oh, and if the point is to show performance differences, “for(i=0 ; i<2147483647; i++);” vx. “for i in xrange(2147483646): pass” ;)

    Reply

Leave a Reply