Instantly share code, notes, and snippets.

# ericnormand/00 Primes in a number.md

Created February 5, 2022 21:51
Show Gist options
• Save ericnormand/d52d1fe0e80f06e4b517d45a082765a0 to your computer and use it in GitHub Desktop.

Primes in a number

Another contrived math problem. This one I think is actually pretty hard. It's got detecting primes, string manipulation, and combinations.

Your task is to write a function that takes an integer and finds all primes that are substrings of the decimal digits of that integer.

Examples

```(find-primes 2) ;=> [2]
(find-primes 22) ;=> [2 2]
(find-primes 717) ;=> [7 7 17 71]
(find-primes 1) ;=> []
(find-primes 44) ;=> []```

Notes:

• Return the primes in ascending order.
• If a prime appears more than once, it should be in the returned sequence that many times.

Thanks to this site for the problem idea, where it is rated Very Hard in Java. The problem has been modified.

### jonasseglare commented Feb 7, 2022

```(defn prime? [x]
(and (not (some #(= 0 (rem x %)) (range 2 x)))
(<= 2 x)))

(defn find-primes [x]
(let [x (str x)]
(->> (subs x j i)
(for [i (range (inc (count x))) j (range i)])
(filter prime?)
sort)))```

### filippocostalli commented Feb 7, 2022 • edited

I know I absolutely need to know more in the clojure core library.
But this solution is clean and smart enough (for me)

```(defn prime? [n]
(and (> n 1) (not-any? (partial divisible? n) (range 2 n))))

(defn primes [s n]
(->> (partition-all n 1 s)
(map #(apply str %))
(filter #(= n (count %)))
(map #(Integer/parseInt %))
(filter #(prime? %))))

(defn find-primes [number]
(let [str (str number)]
(loop [counter (count str)
result []]
(if (= 0 counter)
result
(recur
(- counter 1)
(into [] (sort (concat result (primes str counter)))))))))```

### filippocostalli commented Feb 7, 2022 • edited

@jonasseglare , awesome! The code runs like a charms.
I'm a totally Clojure newbie, may I ask you where i and j come from? Those in the first line of thread-last. You've never declared it.

### jonasseglare commented Feb 7, 2022

@filippocostalli Thanks! The thread-last form is a macro that rewrites code and the code that I wrote expands to the same thing as if I would have written

```(->> (for [i (range (inc (count x))) j (range i)]
(read-string (subs x j i)))
(filter prime?)
sort)```

In other words, the `i` and `j` come from the `(for ...)`. The way I wrote it is not good style, it is just a funny :-D

### mchampine commented Feb 8, 2022

```(defn prime? [n]
(and (< 1 n) (not-any? #(zero? (rem n %)) (range 2 n))))

(defn subseqs [s]
(let [ls (inc (count s))]
(for [b (range ls) e (range (inc b) ls)] (subs s b e))))

(defn find-primes [n]
(sort (filter prime? (map read-string (subseqs (str n))))))```

### miner commented Feb 11, 2022

```(defn prime? [n]
(if (even? n)
(= n 2)
(and (> n 1)
(let [sqrt (Math/sqrt n)]
(loop [candidate 3]
(cond (> candidate sqrt) true
(zero? (rem n candidate)) false
:else (recur (inc (inc candidate)))))))))

(defn find-primes [n]
(let [digs (into () (comp (take-while pos?) (map #(rem % 10))) (iterate #(quot % 10) n))
parts (reduce (fn [ps w] (into ps (partition w 1 digs)))
[]
(range 1 (inc (count digs))))
cands (map #(reduce (fn [r i] (+ (* 10 r) i)) 0 %) parts)]
(sort (filter prime? cands))))```

### miner commented Feb 11, 2022

Transducer version. Use `prime?` from above.

```(defn find-primes [n]
(let [digs (into () (comp (take-while pos?) (map #(rem % 10))) (iterate #(quot % 10) n))]
(transduce (comp (mapcat #(partition % 1 digs))
(map #(reduce (fn [r i] (+ (* 10 r) i)) 0 %))
(filter prime?))
(completing conj! (comp sort persistent!))
(transient [])
(range 1 (inc (count digs))))))```

### miner commented Feb 11, 2022

Inspired by the other solutions, I see that parsing the substrings is faster than doing the math on partitions. Again, using `prime?` from my first example, here is my fastest solution.

```(defn find-primes [n]
(let [s (str n)
c (inc (count s))]
(->> (for [b (range c)
e (range (inc b) c)]
(Long/parseLong (subs s b e)))
(filter prime?)
sort)))```

### vehas commented Mar 17, 2022

I just want to show that for have something more to offer.

```(defn prime? [num]
(and
(not= 1 num)
(every?
(fn [each-num]
(not= 0 (mod num each-num)))
(range 2 (Math/ceil (Math/sqrt num))))))

(defn find-primes [num]
(let [num-str (str num)]
(sort (for [start (range (count num-str))
end (range (inc start)
(inc (count num-str)))
:let [maybe-p (Integer/parseInt (subs num-str start end))]
:when (prime? maybe-p)]
maybe-p))))```

### KingCode commented May 27, 2022 • edited

Sorry for the long-winded solution - will study the very concise and elegant examples above.
In trying for a speedup I used a sieve upfront, windowing for combining digits, and a sorted-in-place vector.

```;; Utilities: a sorted-vector implementation
(defn insert-idx
"Finds the insertion point for x in a sorted vector according to binary pred"
[xs x pred]
(let [cmptor (comparator pred)]
(loop [lo 0 hi (dec (count xs))]
(if (> lo hi)
lo
(let [mid (bit-shift-right (+ lo hi) 1)
midv (nth xs mid)
cmp (cmptor midv x)]
(cond
(< cmp 0)
(recur (inc mid) hi)
(> cmp 0)
(recur lo (dec mid))
:else
mid))))))

(defn sorted-conj
"xs is a sorted vector. Yields a new vector with remaining args conj'ed in the proper
location in increasing order."
([xs y & ys]
(->> ys (cons y)
(reduce (fn [sorted y]
(let [insert-loc (insert-idx sorted y <)]
(-> sorted (subvec 0 insert-loc)
(into [y])
(into (subvec sorted insert-loc (count sorted))))))
xs))))

;; Translation b/w number and digits
(defn n->digs [n]
(loop [n n acc ()]
(let [[q r] [(quot n 10) (rem n 10)]]
(if (zero? n)
acc
(recur (quot n 10) (conj acc r))))))

(defn digs->n [digs]
(->> 1
(iterate (fn [pow]
(* pow 10)))
(map #(* % %2) (reverse digs))
(apply +)))

;; Primality detection
(defn sieve
"Yields a map of integers upto and including n, of whether
the key is a prime (value is :prime), or some product [mult base]
where base is a prime."
[n]
(loop [sieve (sorted-map) x 2]
(cond
(< n x)
sieve
(contains? sieve x)
(recur sieve (inc x))
:else
(-> (into sieve (for [i (range 1 n)
:let [ix (* i x)]
:while (<= ix n)]
[ix [i x]]))
(update x #(when-not (get % x) :prime))
(recur (inc x))))))

(defn primes [sieve]
(->> sieve
(keep (fn [[k v]]
(when (= :prime v)
k)))))

;; Combining digits
(defn windows
"Constructs a lazy seq of all contiguous subsequences of xs."
[xs]
(->> xs (iterate rest)
(sequence (comp (take-while seq)
(mapcat #(reductions conj [] %))
(map seq)
(filter identity)))
(cons ())
lazy-seq))

(defn find-primes [n]
(let [prime? (-> n sieve primes set)
digs (n->digs n)]
(->> digs windows rest
(reduce (fn [acc win]
(let [kand (digs->n win)]
(if (prime? kand)
(sorted-conj acc kand)
acc)))
[]))))

(find-primes 2) ;=> [2]
(find-primes 22) ;=> [2 2]
(find-primes 717) ;=> [7 7 17 71]
(find-primes 1) ;=> []
(find-primes 44) ;=> []```

to join this conversation on GitHub. Already have an account? Sign in to comment