Why the loop is too slow in Racket code

Question

I am trying to find the smallest non-divisor of numbers ( https://codegolf.stackexchange.com/questions/105412/find-the-smallest-number-that-doesnt-divide-n ). The next version using "named let" works correctly:

(define (f1 m) (let loop ((n 2)) (cond [(= 0 (modulo mn)) (loop (+ 1 n))] [else n]))) 

I am testing with

 (f 24) (f 1234567) (f 12252240) (f 232792560) 

A quick output is issued above the version: 5 2 19 and 23.

However, the next version, using the built-in for loop, is very slow and actually crashes with an error from memory with large numbers:

 (define (f2 m) (for/first ((i (range 2 m)) #:when (not (= 0 (modulo mi))) #:final (not (= 0 (modulo mi)))) i)) 

Is there some kind of error in the code of the second version or not for inefficient compared to named let in Racket?

Answer 1

The range function actually distributes the list, so the time for your function prevails in the huge distribution of lists. Use in-range instead:

 (define (f2 m) (for/first ([i (in-range 2 m)] #:when (not (= 0 (modulo mi))) #:final (not (= 0 (modulo mi)))) i)) 

See also the for performance section of the Racket Guide for additional notes on the relative speed of various forms of sequence.

Answer 2

In my opinion, recursion is generally more suitable for Racket than for loops. I would approach the problem this way ...

 (define start-counter 1) (define (f number counter) (cond [(not (= (modulo number counter) 0)) counter] [else (f number (add1 counter))])) (define (f2 number) (f number start-counter))