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.