Q:

Prime generator in Python and C

I have written the Rabin-Miller test in Python and ported it to C. But somehow, the C version is ~20 times slower on my system, and I am not sure how. Anyway, here is my code.
Python
import random
import time

def rabin_miller(n):
    if n in [2, 3, 5]:
        return True
    if n < 2 or n % 2 == 0:
        return False

    s = 0
    d = n - 1
    while d % 2 == 0:
        s += 1
        d >>= 1

    for k in range(2 ** 4):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        c = False
        for r in range(s - 1):
            x = pow(x, 2, n)
            if x == 1:
                return False
            if x == n - 1:
                break
        else:
            return False
    return True

for i in range(10000):
    rabin_miller(i)

C
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

long mod_pow(long b, long e, long m){
    if(m == 1)
        return 0;
    long c = 1;
    for(long i = 0; i < e; i++)
        c = (c * b) % m;
    return c;
}

int rabin_miller(long n){
    if(n == 2 || n == 3)
        return 1;
    if(n < 2 || n % 2 == 0)
        return 0;

    long s = 0, d = n - 1, k = 10, a, x, stop;
    while(d % 2 == 0)
        s += 1, d >>= 1;

    srand(time(NULL));
    for(long i = 0; i < k; i++){
        a = (long) (((float) rand() / RAND_MAX) * (n - 3)) + 2;
        x = mod_pow(a, d, n);
        if(x == 1 || x == n - 1)
            continue;
        stop = 1;
        for(long r = 0; r < s - 1; r++){
            x = mod_pow(x, 2, n);
            if(x == 1)
                return 0;
            if(x == n - 1){
                stop = 0;
                break;
            }
        }
        if(stop){
            return 0;
        }
    }
    return 1;
}

int main(int argc, char *argv[]){
    for(long i = 1; i < 10000; i++){
        rabin_miller(i);
    }
    return 0;
}

A:

I believe the problem is that long mod_pow is very inefficient, as it takes e steps to complete, as compared to Python's approach which likely only takes log(e) steps. To fix this, you should use an algorithm similar to the following
function modular_pow(base, exponent, modulus)
if modulus = 1 then return 0
Assert :: (modulus - 1) * (modulus - 1) does not overflow base
result := 1
base := base mod modulus
while exponent > 0
    if (exponent mod 2 == 1):
       result := (result * base) mod modulus
    exponent := exponent >> 1
    base := (base * base) mod modulus
return result

A:

I see a number of things that may help you improve your C program in addition to the review from Oscar Smith which correctly identifies the reason for the major performance difference in the two versions.
Use better variable names
Single letter variable names are not descriptive and not helpful to the reader of the code.  
Only call srand once
The call to srand should only be done once.  Calling it multiple times does not improve randomness.
Use bool where appropriate
Since C99, the C language supports bool, and the rabin_miller() function should return a bool rather than an int.  You will need to #include <stdbool.h> to do this.
Use the appropriate data type
In the original code k and i are just used as part of a loop count.  An int or unsigned would be a more appropriate type than long and may confer a performance advantage.  The same goes for r and s.
Prefer for to while
The code which calculates s and d could be written a bit more succinctly and clearly, in my view, like this:
for(s = 0; d % 2 == 0; ++s) {
    d >>= 1;
}

Simplify for loop termination condition
The point to the for (r ... loop is to simply iterate s-1 times.  Rather than comparing r to s-1 each iteration, it makes more sense to simply start the loop from 1 rather than 0 and compare with s directly:
    for(unsigned r = 1; r < s; r++) {

Even simpler, count down instead.  Some processors have a special instruction which does both a decrement and test for zero so here again, there may be a performance advantage on some architectures:
    for(unsigned r = s; r; --r) {

Declare variables in as small a scope as practical
The variables a and x are only used inside the big loop and so could easily be declared only there.  Keeping the scope of variables as small as practical makes the code easier to read and understand and may give the compiler some better hints as to register allocation.

