Simple prime number test 1000 slower than trivial python?

New to Julia
1

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.

2

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
3

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
4

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
5

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.

9 Likes
6

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.