GCJJ Practice2

gcj_prac2.clj

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; prime nums

(defn sieve [n]
  (let [n (int n)]
    "Returns a list of all primes from 2 to n"
    (let [root (int (Math/round (Math/floor (Math/sqrt n))))]
      (loop [i (int 3)
	     a (int-array n)
	     result (list 2)]
	(if (>= i n)
	  (reverse result)
	  (recur (+ i (int 2))
		 (if (< i root)
		   (loop [arr a
			  inc (+ i i)
			  j (* i i)]
		     (if (>= j n)
		       arr
		       (recur (do (aset arr j (int 1)) arr)
			      inc
			      (+ j inc))))
		   a)
		 (if (zero? (aget a i))
		   (conj result i)
		   result)))))))




;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; prime list
(let [prime-max 1000000
      prime-list  (sieve prime-max)]

  (defn prime-list-between [n m]
    (if (> n prime-max)
      (do (println "Warning: I have no more than " prime-max " primes.")
	  prime-list)
      (drop-while (fn [x] (< x n))
		  (take-while (fn [y] (<= y m)) prime-list))))

)


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; another logic reviced

(defn set-arr [arr start-index end-index inc-val new-val]
  (loop [arr arr, idx start-index, num-list []]
    (if (> idx end-index)
      [arr (distinct num-list)]
      (let [^long val-now (aget arr idx)
	    new-num-list (if (not= val-now (long 0))
			   (conj num-list val-now)
			   num-list)]
	(recur (do (aset ^longs arr idx (long new-val))
		   arr)
	       (+ idx inc-val)
	       new-num-list)))))

(defn reset-arr [arr num-list new-val]
  (amap ^longs arr idx new-arr
	(if (some #(= % (aget ^longs arr idx)) num-list)
	  (long new-val)
	  (aget ^longs arr idx))))
      


(defn get-sol [col]
  (+ (count (filter zero? col))
     (count (distinct (filter (complement zero?) col)))))


(defn gcj-prac2_4 [A B P]
  (loop [prime-list (prime-list-between P (- B A))
         arr (long-array (inc (- B A)) (long 0))
         counter (long 1)]
    (if (empty? prime-list)
      (get-sol (vec arr))
      (let [tgt-prime (first prime-list)
            first-multiple (if (= (rem A tgt-prime) 0)
                             A
                             (+ A (- tgt-prime (rem A tgt-prime))))
	    [arr-step1 num-to-change] (set-arr arr
					       (- first-multiple A)
					       (- B A)
					       tgt-prime
					       counter)
	    arr-step2 (reset-arr arr-step1 counter num-to-change)]
        (recur (next prime-list)
               arr-step2
               (inc counter))))))

First version is tooooo slow to solve large set. It needs over 5 hours.

Second one ends by 11 minutes, but has bug.

Third version is not tested yet.