Square-free integers: Difference between revisions
Content added Content deleted
Line 1,398: | Line 1,398: | ||
Total count of square-free numbers between 1000000000000 and 1000000000145: 89 |
Total count of square-free numbers between 1000000000000 and 1000000000145: 89 |
||
</pre> |
</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}}== |
=={{header|REXX}}== |