;Helpers

;Compile and load this program
(defun comp()
	(compile-file "leapfrog.lisp")
	(load "leapfrog.fas"))

;Similiar to C's -> operator, except really it's the '.' operator. What would have said "map->what" or "map.what" in C is now "-> map what"
(defmacro -> (map key)
  `(gethash ,key ,map))

(defmacro while (condition &rest body)
  `(loop (unless ,condition (return)) ,@body))

;Add an item to the end of a list, not the 
(defmacro pushback(map value)
	`(if (not(car ,map))
		(setf ,map (push ,value ,map))
		(insert-after ,value ,map (-(length ,map)1))))

(defun insert-after (newelt list index)
 "Insert NEWELT in LIST after the INDEXth cell.
 Returns LIST."
 (push newelt (cdr (nthcdr index list)))
 list)

;From On Lisp
(defmacro for ((var start stop) &body body)
  (let ((gstop (gensym)))
    `(do ((,var ,start (1+ ,var))
          (,gstop ,stop))
         ((> ,var ,gstop))
       ,@body)))

;Nice, the slow way! But it only goes up to the square root which is not so bad
(defun is-prime(primes prime?)
	(let ((max (sqrt prime?)))
		(dolist (prime primes)
			(when (> prime max)
				(return))
			(when (typep (/ prime? prime) 'integer)
				(return-from is-prime NIL))))
	T)

;The Main Course

;New 'general' algorithm for experimental wave-following prime finder:

;The basic idea is, you don't go through every composite and see if it's prime - you step every prime along, like moving a draught piece along an infinitely long chess board 1 square wide (and infinitely high), and completely skip the composite checking! Any numbers not hopped onto (eg, they are hopped over) by the existing draught pieces are prime and they get their own piece which then hops along with the others.

;The distance for any of the pieces to hop is >= the highest piece hopping once. This ensures all the pieces remain synchronised and thus the mini-table stays of a size no greater than the number of the highest piece. Some of the pieces will pile on top of one another, this is fine, as the board is infinitely high.

;We can show all the factors below the square root of a composite, if its corresponding entry in the mini-table is a list of the primes hopped onto that composite (which it is in the code below).

(defun leapfrog(start end &optional show-composite-factors helper)
	(let ((v (make-hash-table)) (primes) (new-primes) (count 0) (pointer start))

	;How to make it recursive:
	;	1.Call leapfrog to get the primes up to the sqrt of start with recursion flag 'helper' = t
	;		2.leapfrog, when called with recursive flag set, will start with primes 2 and 3 and start from number 4, and go on till the end
	;	3.When the recursed leapfrog returns, it will return a list of primes up to the sqrt of start, as expected, and then we go to the end
	(if (not helper)
		(progn
			(setf primes (leapfrog 2 (sqrt start) NIL T))
			(push 2 primes))
		(progn
			(setf primes (list 2))))

;	(format t "Looking for primes from ~d to ~d~%" start end)
	;For every prime up to the start
	(dolist (prime primes)
		;Each prime's variable (-> v) starts off as the nearest divisor of the prime into the start address
		;1.We can get rid of this line's subtraction [no we can't]
		(setf (-> v prime) (* (-(round(/ start prime))1) prime)))
		;2.And replace it with this
;		(setf (-> v prime) (* (round(/ start prime)) prime)))
	;3.If we do this
;	(incf pointer)

	;Keep going until the end
	(let ((mini-table (make-hash-table)) (last))
		(while (<= pointer end)
			;With the leapfrog method, we start by adding the prime to its variable
			(let ((lastprime (first(last primes))))
				(incf (-> v lastprime) lastprime)
				(if show-composite-factors
					(push lastprime (-> mini-table (-> v lastprime)))
					(setf (-> mini-table (-> v lastprime))T))
				(setf last (-> v lastprime))
				;Now, we go backwards through all the lower primes until the lowest, and each variable leapfrogs above the last one, meaning that the lowest prime is always at the end afterwards (not sure if this is the most efficient way). Leapfrogging is more than one step, until it reaches its goal
					(dolist (prime (rest(reverse primes)))
						(while (<= (-> v prime) (-> v lastprime))
							;Every time we hit a multiple of a prime, we put it in a hashtable, or rather, the prime that makes up a factor of it (for showing factors later)
							(incf (-> v prime)prime)
							(if show-composite-factors
								(push prime (-> mini-table (-> v prime)))
								(setf (-> mini-table (-> v prime))T))
							(setf last (-> v prime)))))
			;This is a little bit of logic to deal with expanding the search space. New primes are introduced *only* when we encounter their value squared, not earlier (eg, 3 is only introduced when we hit 9). This logic works a treat, because the theory is proven in the paper. This code comes *before* we look for primes in mini-table
			(let ((last-prime (first(last primes))))
				(for (prime (+ last-prime 1) (* last-prime 2))
					(when (and (>= (* prime prime) pointer) (< (* prime prime) last)
						(or (find prime new-primes)
							;Only look for primes below the start address (to speed things up by not checking for these stragglers all the time)
							(and(< prime start)
								(is-prime primes prime))))
						(pushback primes prime)
						(if show-composite-factors
							(setf (-> mini-table (* prime prime)) (list prime))
							(setf (-> mini-table (* prime prime)) T))
						(setf (-> v prime)(* prime prime))))
				;Now we go through the entire block defined by the lowest prime leapfrogged, and the highest prime leapfrogged. We look for primes, which are defined as the numbers which had no corresponding multiple of a prime
				(for (i pointer last)
					(when (> i end)
						(return))
					;If there is no entry i stored in the table, it is prime, because it is not a multiple of any prime. Print it, add it.
					(unless (-> mini-table i)
						(when (>= i start)
;							(format t "~d ~d~%" i count)
							(incf count)
							(push i new-primes)))
					;The composite had factors stored in the table corresponding to this number i, so print them if the option is specified. Finally, delete the composite from the mini-table to save on memory.
					(when (-> mini-table i)
						(when show-composite-factors
							(when (and (equal start end) (equal start i))
								(return-from leapfrog (-> mini-table i)))
;							(format t "~d has factors ~a~%" i (remove-duplicates(-> mini-table i)))
						)
						(remhash i mini-table))
				)
				(setf pointer (+ last 1))
	)))
;Return the variables table (useless), the primes (useless) and the primes found between start and end (useful)
(nreverse new-primes)))