Finding next prime Number

random
, ,
1

What happens

I’m solving Problem 157 from Codeabbey, which is about finding the next prime from a starting number and also check if is emirp, which means, the reversed number must be also prime.

The main concern of this post is just about finding the next prime.

What do you understand or find about that problem

After discovered recursion and TOC in hy is impossible to don’t use it. Nontheless, iterative methods are still slow. I’ve poking around and found information about non deterministic methods, however I don’t feel might be able to do it … but…there is another way to optimize this algorithm?

You make any workaround? What did you do?

Yes, at first glance I created a code that prints primes numbers and tooks almost a minute to compute the first ten thousand primes. After finding some shorcuts, now it takes less than 15 seconds, which is an improve.

With that improve in mind I make the code attached to this post. The input of the main function is a integer and a limit (meanwhile). It increase the number by 1 until finding the next prime.

Evidences

Code

(require [hy.contrib.loop [loop]])
;Return true or false
(defn isPrime[number]
  (if (and (< number 4) (>= number 2))
    True
    (if (= (% number 2) 0)
      False
      (do
        (setv max (// (- number 1) 2))
        (loop [[j max] [divisor 2]]
          (if (> (* divisor divisor) number)
            True
            (if (= (% number (+ (* 2 divisor) 1)) 0)
              False
              (recur (dec j) (inc divisor)))))))))

;Function to generate the serie
(defn findNextPrime[startValue limit]
  (loop [[i startValue]]
    (if (isPrime i)
      (print i)
      (if (> i limit)
        (print "Not founded")
        (recur (inc i))))))

; Meanwhile the code is finished i put a limit
; I defined the limit as the double of the input
(findNextPrime 8454965 (* 8454965 2))
(findNextPrime 10 (* 10 2))
(findNextPrime 20 (* 20 2))
(findNextPrime 50(* 50 2))

Output

8455011
11
23
51

I need help with

With integers as the example it finds easily the next prime. But when a number like 30518758619308176598765 (which is an input from CodeAbbey) is entered, it never finds the next prime.

I’ll be really grateful if any idea is suggested or any comprehensible documentation is provided, because I feel like I’m walking on unknown roads, and I want to solve this problem.

2

One of the efficents ways to solve this challenge is via non deterministic methods. The Miller-Rabin Test is a good way to approach the challenge.

Here I found the fastest way to verify number is a prime. However, this specific problem ask for a Emirp, which is a palindrome prime.

The inputs are size 10^23 so if a number starts in 2, 4, 5, 6, 8 to reach the nex Emirp we will need to iterate over 10^23 values, which is absurd, so the algorith should handle this.

1 Like