Prime generator in Python and C
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 &gt; 0
    if (exponent mod 2 == 1):
       result := (result * base) mod modulus
    exponent := exponent &gt;&gt; 1
    base := (base * base) mod modulus
return result