Square-free integers: Difference between revisions
→{{header|Racket}}
Line 1,398:
Total count of square-free numbers between 1000000000000 and 1000000000145: 89
</pre>
=={{header|Racket}}==
This includes unit tests to demonstrate that 1000000145 **isn't** square-free.
See discussion.
<lang racket>#lang racket
(define (not-square-free-set-for-range range-min (range-max (add1 range-min)))
(for*/set ((i2 (sequence-map sqr (in-range 2 (add1 (integer-sqrt range-max)))))
(i2.x (in-range (* i2 (quotient range-min i2))
(* i2 (add1 (quotient range-max i2)))
i2))
#:when (and (<= range-min i2.x)
(< i2.x range-max)))
i2.x))
(define (square-free? n #:table (table (not-square-free-set-for-range n)))
(not (set-member? table n)))
(define (count-square-free-numbers #:range-min (range-min 1) range-max)
(- range-max range-min (set-count (not-square-free-set-for-range range-min range-max))))
(define ((print-list-to-width w) l)
(let loop ((l l) (x 0))
(if (null? l)
(unless (zero? x) (newline))
(let* ((str (~a (car l))) (len (string-length str)))
(cond [(<= (+ len x) w) (display str) (write-char #\space) (loop (cdr l) (+ x len 1))]
[(zero? x) (displayln str) (loop (cdr l) 0)]
[else (newline) (loop l 0)])))))
(define print-list-to-80 (print-list-to-width 80))
(module+ main
(print-list-to-80 (for/list ((n (in-range 1 (add1 145))) #:when (square-free? n)) n))
(print-list-to-80 (time (let ((table (not-square-free-set-for-range #e1e9 (add1 (+ #e1e9 145)))))
(for/list ((n (in-range #e1e9 (add1 (+ #e1e9 145))))
#:when (square-free? n #:table table)) n))))
(displayln "Compare time taken without the table (rather with table on the fly):")
(void (time (for/list ((n (in-range #e1e9 (add1 (+ #e1e9 145)))) #:when (square-free? n)) n)))
(count-square-free-numbers 100)
(count-square-free-numbers 1000)
(count-square-free-numbers 10000)
(count-square-free-numbers 100000)
(count-square-free-numbers 1000000))
(module+ test
(require rackunit)
(require math/number-theory)
(check-false (square-free? 1000000145))
(factorize 1000000145)
(check-not-false (member '(61 2) (factorize 1000000145))))</lang>
{{out}}
<pre>1 2 3 5 6 7 10 11 13 14 15 17 19 21 22 23 26 29 30 31 33 34 35 37 38 39 41 42 43
46 47 51 53 55 57 58 59 61 62 65 66 67 69 70 71 73 74 77 78 79 82 83 85 86 87 89
91 93 94 95 97 101 102 103 105 106 107 109 110 111 113 114 115 118 119 122 123
127 129 130 131 133 134 137 138 139 141 142 143 145
cpu time: 47 real time: 45 gc time: 15
1000000001 1000000002 1000000003 1000000005 1000000006 1000000007 1000000009
1000000010 1000000011 1000000013 1000000014 1000000015 1000000018 1000000019
1000000021 1000000022 1000000027 1000000029 1000000030 1000000031 1000000033
1000000034 1000000037 1000000038 1000000039 1000000041 1000000042 1000000043
1000000045 1000000046 1000000047 1000000049 1000000051 1000000054 1000000055
1000000057 1000000058 1000000059 1000000061 1000000063 1000000065 1000000066
1000000067 1000000069 1000000070 1000000073 1000000074 1000000077 1000000078
1000000079 1000000081 1000000082 1000000083 1000000086 1000000087 1000000090
1000000091 1000000093 1000000094 1000000095 1000000097 1000000099 1000000101
1000000102 1000000103 1000000105 1000000106 1000000109 1000000110 1000000111
1000000113 1000000114 1000000115 1000000117 1000000118 1000000119 1000000121
1000000122 1000000123 1000000126 1000000127 1000000129 1000000130 1000000131
1000000133 1000000135 1000000137 1000000138 1000000139 1000000141 1000000142
Compare time taken without the table (rather with table on the fly):
cpu time: 7781 real time: 7865 gc time: 1955
61
608
6083
60794
607926</pre>
=={{header|REXX}}==
| |||