import scala.collection.immutable.Queue
import scala.annotation.tailrec
 
object Main extends App {
 
	var t = System.currentTimeMillis
 
	def primes(n: Int) = {
		@tailrec
		def divisibleByAny(x: Int, list: Queue[Int]): Boolean = {
			if (list.isEmpty) false else {
				val (h, t) = list.dequeue
				h * h <= x && (x % h == 0 || divisibleByAny(x, t))
			}
		}
		@tailrec
		def morePrimes(from: Int, prev: Queue[Int]): Queue[Int] = {
			if (prev.size == n) prev else
				morePrimes(from + 2, if (divisibleByAny(from, prev)) prev else prev.enqueue(from))
		}
		morePrimes(3, Queue(2))
	}
 
	System.out.println(primes(3000).last);
	t = System.currentTimeMillis - t
	System.out.println(t + "ms");
 
}

aW1wb3J0IHNjYWxhLmNvbGxlY3Rpb24uaW1tdXRhYmxlLlF1ZXVlCmltcG9ydCBzY2FsYS5hbm5vdGF0aW9uLnRhaWxyZWMKCm9iamVjdCBNYWluIGV4dGVuZHMgQXBwIHsKCgl2YXIgdCA9IFN5c3RlbS5jdXJyZW50VGltZU1pbGxpcwoJCglkZWYgcHJpbWVzKG46IEludCkgPSB7CgkJQHRhaWxyZWMKCQlkZWYgZGl2aXNpYmxlQnlBbnkoeDogSW50LCBsaXN0OiBRdWV1ZVtJbnRdKTogQm9vbGVhbiA9IHsKCQkJaWYgKGxpc3QuaXNFbXB0eSkgZmFsc2UgZWxzZSB7CgkJCQl2YWwgKGgsIHQpID0gbGlzdC5kZXF1ZXVlCgkJCQloICogaCA8PSB4ICYmICh4ICUgaCA9PSAwIHx8IGRpdmlzaWJsZUJ5QW55KHgsIHQpKQoJCQl9CgkJfQoJCUB0YWlscmVjCgkJZGVmIG1vcmVQcmltZXMoZnJvbTogSW50LCBwcmV2OiBRdWV1ZVtJbnRdKTogUXVldWVbSW50XSA9IHsKCQkJaWYgKHByZXYuc2l6ZSA9PSBuKSBwcmV2IGVsc2UKCQkJCW1vcmVQcmltZXMoZnJvbSArIDIsIGlmIChkaXZpc2libGVCeUFueShmcm9tLCBwcmV2KSkgcHJldiBlbHNlIHByZXYuZW5xdWV1ZShmcm9tKSkKCQl9CgkJbW9yZVByaW1lcygzLCBRdWV1ZSgyKSkKCX0KCQoJU3lzdGVtLm91dC5wcmludGxuKHByaW1lcygzMDAwKS5sYXN0KTsKCXQgPSBTeXN0ZW0uY3VycmVudFRpbWVNaWxsaXMgLSB0CglTeXN0ZW0ub3V0LnByaW50bG4odCArICJtcyIpOwoKfQ==