# Improving performance in checking prime numbers

**URL:** <https://discourse.julialang.org/t/improving-performance-in-checking-prime-numbers/56365>\
**Category:** General Usage\
**Created:** [March 2, 2021, 8:56pm UTC](https://discourse.julialang.org/t/improving-performance-in-checking-prime-numbers/56365 "2021-03-02T20:56:01Z")\
**Posts on this page:** 15\
**Page:** 1

<div class="post-metadata">

**Author:** ![dariush-bahrami](https://avatars.discourse-cdn.com/v4/letter/d/f1d935/32.png) [@dariush-bahrami](https://discourse.julialang.org/u/dariush-bahrami)\
**Post date:** [March 2, 2021, 8:56pm UTC](https://discourse.julialang.org/t/improving-performance-in-checking-prime-numbers/56365/1 "2021-03-02T20:56:01Z")

</div>

Hi, I wrote the following code in python with help of numba JIT:

```julia
from numba import jit

@jit(nopython=True)
def is_prime(number):
    upper_limit = int(number**0.5) + 1
    for i in range(2, upper_limit):
        if number % i:
            return False
    return True

number = 23002999

is_prime(number)

```

By timing this code in jupyter with `timeit` magic the following result I get:

```julia
394 ns ± 10.9 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

```

For my project I need more performance so I decide to use Julia; The following is my julia code:

```julia
using BenchmarkTools

function isprime(number)
    upper_limit = trunc(Int, sqrt(number)) + 1
    for i in 2:upper_limit
        if number % i == 0
            return false
        end
    end
    return true
end

number = 23002999
isprime(number)

```

by using `@benchmark` macro I get the following results:

```julia
BenchmarkTools.Trial: 
  memory estimate: 0 bytes
  allocs estimate: 0
  --------------
  minimum time: 40.100 μs (0.00% GC)
  median time: 40.200 μs (0.00% GC)
  mean time: 43.025 μs (0.00% GC)
  maximum time: 1.796 ms (0.00% GC)
  --------------
  samples: 10000
  evals/sample: 1

```

Definitely something is wrong with my code; Do you have any suggestions for better performance? Thank you in advance.

---

<div class="post-metadata">

**Author:** ![fabiangans](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fabiangans/32/2624_2.png) [@fabiangans](https://discourse.julialang.org/u/fabiangans)\
**Post date:** [March 2, 2021, 9:11pm UTC](https://discourse.julialang.org/t/improving-performance-in-checking-prime-numbers/56365/2 "2021-03-02T21:11:17Z")

</div>

I think the bug is in the python code, I think it should be `if number % i == 0:` to let the algorithm actually do something.

---

<div class="post-metadata">

**Author:** ![dariush-bahrami](https://avatars.discourse-cdn.com/v4/letter/d/f1d935/32.png) [@dariush-bahrami](https://discourse.julialang.org/u/dariush-bahrami)\
**Post date:** [March 2, 2021, 9:13pm UTC](https://discourse.julialang.org/t/improving-performance-in-checking-prime-numbers/56365/3 "2021-03-02T21:13:12Z")

</div>

You are absolutely right, after fixing this the result is:

```julia
51.6 µs ± 3.31 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

```

---

<div class="post-metadata">

**Author:** ![Henrique\_Becker](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/henrique_becker/32/15443_2.png) [@Henrique\_Becker](https://discourse.julialang.org/u/Henrique_Becker)\
**Post date:** [March 2, 2021, 9:18pm UTC](https://discourse.julialang.org/t/improving-performance-in-checking-prime-numbers/56365/4 "2021-03-02T21:18:52Z")

</div>

You cannot use solutions provided by packages for this project? It seems strange to be worried about performance of `isprime` and not using a polished library to do the work.

---

<div class="post-metadata">

**Author:** ![ImreSamu](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/imresamu/32/20677_2.png) [@ImreSamu](https://discourse.julialang.org/u/ImreSamu)\
**Post date:** [March 2, 2021, 9:23pm UTC](https://discourse.julialang.org/t/improving-performance-in-checking-prime-numbers/56365/5 "2021-03-02T21:23:27Z")

</div>

yes

> [@Henrique\_Becker](#):
>
> `isprime`

agree …  
the JuliaMath / Primes package solutions is:

> <https://github.com/JuliaMath/Primes.jl/blob/main/src/Primes.jl#L144>

---

<div class="post-metadata">

**Author:** ![dariush-bahrami](https://avatars.discourse-cdn.com/v4/letter/d/f1d935/32.png) [@dariush-bahrami](https://discourse.julialang.org/u/dariush-bahrami)\
**Post date:** [March 2, 2021, 9:26pm UTC](https://discourse.julialang.org/t/improving-performance-in-checking-prime-numbers/56365/6 "2021-03-02T21:26:08Z")

</div>

I need an unconventional parameter to analyze the distribution of prime numbers. To write the code for calculating that parameter, I need to get a better understanding of how to increase performance. I am currently testing different ways to implement it.

---

<div class="post-metadata">

**Author:** ![dariush-bahrami](https://avatars.discourse-cdn.com/v4/letter/d/f1d935/32.png) [@dariush-bahrami](https://discourse.julialang.org/u/dariush-bahrami)\
**Post date:** [March 2, 2021, 9:33pm UTC](https://discourse.julialang.org/t/improving-performance-in-checking-prime-numbers/56365/7 "2021-03-02T21:33:40Z")

</div>

Is this in standard library?

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [March 2, 2021, 9:43pm UTC](https://discourse.julialang.org/t/improving-performance-in-checking-prime-numbers/56365/8 "2021-03-02T21:43:40Z")

</div>

It’s in `Primes.jl` (which you can install using the package manager). Also, it’s worth noting that finding a large number of of primes using a sieve may be better for what you’re describing.

---

<div class="post-metadata">

**Author:** ![Mason](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mason/32/2423_2.png) [@Mason](https://discourse.julialang.org/u/Mason)\
**Post date:** [March 2, 2021, 10:08pm UTC](https://discourse.julialang.org/t/improving-performance-in-checking-prime-numbers/56365/9 "2021-03-02T22:08:01Z")

</div>

Since you picked a prime number in your example that was big enough to profit from multithreading, here’s a multithreaded version of your `isprime`:

```julia
julia> using Transducers

julia> function isprime_xt(number)
           upper_limit = trunc(Int, sqrt(number)) + 1
           init=false
           basesize = 2*upper_limit ÷ Threads.nthreads()
           foldxt(right, ReduceIf(x -> x === false), 2:upper_limit |> Map(i -> number % i != 0); init, basesize)
       end
isprime_xt (generic function with 1 method)

julia> function isprime(number)
           upper_limit = trunc(Int, sqrt(number)) + 1
           for i in 2:upper_limit
               if number % i == 0
                   return false
               end
           end
           return true
       end
isprime (generic function with 1 method)

julia> let n = Ref(23002999)
           @btime isprime($n[]) 
           @btime isprime_xt($n[])
       end
  25.299 μs (0 allocations: 0 bytes)
  10.009 μs (32 allocations: 2.30 KiB)
true

```

I suspect that a _much_ faster version could be made with a bit of effort by chunking the search range into blocks of some multiple of 8 or 16 and then taking advantage of LoopVectorization.jl in each chunk, rather than multi-threading. Then the outer part could be profitably multithreaded too.

---

<div class="post-metadata">

**Author:** ![Mason](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mason/32/2423_2.png) [@Mason](https://discourse.julialang.org/u/Mason)\
**Post date:** [March 2, 2021, 10:10pm UTC](https://discourse.julialang.org/t/improving-performance-in-checking-prime-numbers/56365/10 "2021-03-02T22:10:21Z")

</div>

Oh, I should also mention that though this multi-threaded approach _does_ get early termination, it still won’t terminate as fast as the sequential one, so there’s a real overhead for numbers that are like a multiple of two.

```julia
julia> let n = Ref(23002999 + 1)
           @btime isprime($n[]) 
           @btime isprime_xt($n[])
       end
  6.419 ns (0 allocations: 0 bytes)
  4.911 μs (24 allocations: 1.77 KiB)
false

```

A smarter approach might be to do the first chunk of integers sequentially.

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [March 2, 2021, 10:10pm UTC](https://discourse.julialang.org/t/improving-performance-in-checking-prime-numbers/56365/11 "2021-03-02T22:10:59Z")

</div>

For problems like factoring primes, it’s probably worth pursuing algorithmic improvements before micro-optimizations. The best system will probably be some combination of trial division by small factors in tandem with a probabilistic prime test

---

<div class="post-metadata">

**Author:** ![Mason](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mason/32/2423_2.png) [@Mason](https://discourse.julialang.org/u/Mason)\
**Post date:** [March 2, 2021, 10:12pm UTC](https://discourse.julialang.org/t/improving-performance-in-checking-prime-numbers/56365/12 "2021-03-02T22:12:00Z")

</div>

Sure, but that’s not what the OP asked for, and I don’t know anything about algorithmic improvements to the OP’s code anyways. 🙂

---

<div class="post-metadata">

**Author:** ![dariush-bahrami](https://avatars.discourse-cdn.com/v4/letter/d/f1d935/32.png) [@dariush-bahrami](https://discourse.julialang.org/u/dariush-bahrami)\
**Post date:** [March 2, 2021, 10:16pm UTC](https://discourse.julialang.org/t/improving-performance-in-checking-prime-numbers/56365/13 "2021-03-02T22:16:07Z")

</div>

Thank you; I am planning to use Sieve of Eratosthenes; but may be with some search I can find a better algorithm for large primes.

---

<div class="post-metadata">

**Author:** ![dariush-bahrami](https://avatars.discourse-cdn.com/v4/letter/d/f1d935/32.png) [@dariush-bahrami](https://discourse.julialang.org/u/dariush-bahrami)\
**Post date:** [March 2, 2021, 10:24pm UTC](https://discourse.julialang.org/t/improving-performance-in-checking-prime-numbers/56365/14 "2021-03-02T22:24:35Z")

</div>

Thank you very much for your suggestion. To understand your code, I need to study multithreading; Your code performance makes me very eager to learn it as soon as possible.

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [March 2, 2021, 10:25pm UTC](https://discourse.julialang.org/t/improving-performance-in-checking-prime-numbers/56365/15 "2021-03-02T22:25:36Z")

</div>

Depending on how large large is, there are asymtotically more efficient sieves such as the Quadratic sieve or the General Number Field sieve.