# Simple prime number test 1000 slower than trivial python?

Julia code:

``````function isprime(n)
for i = 1:Int(floor(sqrt(n)))
if n % i == 0
return false
end
end
return true
end
@time isprime(10000001829379821798314198278324234)
``````

`0.025277 seconds (62.29 k allocations: 2.892 MiB)`

Python:

``````import math, time

def isprime(n):
for i in range(1,int(math.sqrt(n))):
if n%i == 0:
return False
return True
start = time.process_time()
print(isprime(10000001829379821798314198278324234))
end = time.process_time() - start
print(end)
``````
``````False
1.6626999999998227e-05
``````

Edit: `@btime` gives 24 ns which is faster than python, I guess `@time` is something totally different.

Your timing includes the compile time. If you run it again you get:

`````` 0.000005 seconds (4 allocations: 160 bytes)
``````

But better use BenchmarkTools:

``````julia> using BenchmarkTools

julia> @btime isprime(10000001829379821798314198278324234)
29.827 ns (0 allocations: 0 bytes)
false
``````

And also read the performance tips section of the manual.

2 Likes

Also, your loop needs to start at 2:

``````julia> function isprime(n)
for i = 2:Int(floor(sqrt(n)))
if n % i == 0;
return false
end
end
return true
end
isprime (generic function with 1 method)

julia> using BenchmarkTools

julia> @btime isprime(999331)
4.386 μs (0 allocations: 0 bytes)
true
``````
1 Like

Actually, you need to take care here. Firstly, your input value is so large that it’s not an `Int`, it’s an `Int128`:

``````julia> typeof(10000001829379821798314198278324234)
Int128
``````

The square root is not outside the range of `Int64`, but with larger inputs you can get into trouble.

And secondly: `Int(floor(sqrt(n)))`, gives you the wrong number:

``````julia> n = 10000001829379821798314198278324234
10000001829379821798314198278324234

julia> Int(floor(sqrt(n)))  # you should rather use floor(Int, sqrt(n)), actually
100000009146898688

julia> isqrt(n) # this is the largest integer m such that m^2 < n
100000009146898690
``````
2 Likes

Also, your example input is an even number, so it will exit on the first division test, so it’s not a good test number. And, if you actually choose a prime number that big, your algorithm would take incredibly long to return.

Compare this with the function from the Primes package:

``````julia> using Primes

julia> p = nextprime(10^18)
1000000000000000003

julia> @time isprime1(p)  # I renamed your function to isprime1
8.941389 seconds (4 allocations: 160 bytes)
true

julia> @time isprime1(p)
8.977674 seconds (4 allocations: 160 bytes)
true

julia> @time isprime(p)  # this is the function from the Primes package
0.000163 seconds (4 allocations: 160 bytes)
true
``````

Your input is ~10^35, so you can imagine that it would take a very long time to return.

8 Likes

That’s very correct I wasn’t paying enough attention. Great work on the `Primes.jl`!

After using `1000000000000000003` and correct the starting pint of the loop, Julia spits `7.9 s` and Python uses `77.9 s`.