# Simple prime number test 1000 slower than trivial python?

**URL:** <https://discourse.julialang.org/t/simple-prime-number-test-1000-slower-than-trivial-python/15504>\
**Category:** New to Julia\
**Tags:** question\
**Created:** [September 26, 2018, 9:22am UTC](https://discourse.julialang.org/t/simple-prime-number-test-1000-slower-than-trivial-python/15504 "2018-09-26T09:22:15Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![jling](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jling/32/212909_2.png) [@jling](https://discourse.julialang.org/u/jling)\
**Post date:** [September 26, 2018, 9:22am UTC](https://discourse.julialang.org/t/simple-prime-number-test-1000-slower-than-trivial-python/15504/1 "2018-09-26T09:22:15Z")

</div>

Julia code:

```nohighlight
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:

```nohighlight
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)

```

```julia
False
1.6626999999998227e-05

```

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

---

<div class="post-metadata">

**Author:** ![mauro3](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mauro3/32/292_2.png) [@mauro3](https://discourse.julialang.org/u/mauro3)\
**Post date:** [September 26, 2018, 9:25am UTC](https://discourse.julialang.org/t/simple-prime-number-test-1000-slower-than-trivial-python/15504/2 "2018-09-26T09:25:36Z")

</div>

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

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

```

But better use BenchmarkTools:

```julia
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.

---

<div class="post-metadata">

**Author:** ![mauro3](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mauro3/32/292_2.png) [@mauro3](https://discourse.julialang.org/u/mauro3)\
**Post date:** [September 26, 2018, 9:35am UTC](https://discourse.julialang.org/t/simple-prime-number-test-1000-slower-than-trivial-python/15504/3 "2018-09-26T09:35:30Z")

</div>

Also, your loop needs to start at 2:

```julia
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                                                                                                                                                                   

```

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [September 26, 2018, 10:27am UTC](https://discourse.julialang.org/t/simple-prime-number-test-1000-slower-than-trivial-python/15504/4 "2018-09-26T10:27:25Z")

</div>

> [@jling](#):
>
> `for i = 1:Int(floor(sqrt(n)))`

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
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
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

```

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [September 26, 2018, 10:55am UTC](https://discourse.julialang.org/t/simple-prime-number-test-1000-slower-than-trivial-python/15504/5 "2018-09-26T10:55:50Z")

</div>

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
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.

---

<div class="post-metadata">

**Author:** ![jling](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jling/32/212909_2.png) [@jling](https://discourse.julialang.org/u/jling)\
**Post date:** [September 26, 2018, 3:08pm UTC](https://discourse.julialang.org/t/simple-prime-number-test-1000-slower-than-trivial-python/15504/6 "2018-09-26T15:08:51Z")

</div>

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`.