Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
461 PurelyFunctional.tv Newsletter

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.

Please submit your solutions as comments on this gist.

To subscribe: https://purelyfunctional.tv/newsletter/

@jonasseglare
Copy link

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)
         read-string
         (for [i (range (inc (count x))) j (range i)])
         (filter prime?)
         sort)))

@filippocostalli
Copy link

filippocostalli commented Feb 7, 2022

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

filippocostalli commented Feb 7, 2022

@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
Copy link

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

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

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

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

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

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

KingCode commented May 27, 2022

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) ;=> []

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