Square-free integers: Difference between revisions
Content added Content deleted
m (→{{header|Racket}}: flagged as incorrect.) |
(→{{header|Racket}}: up from a billion to a trillion) |
||
Line 1,400: | Line 1,400: | ||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
{{incorrect|Racket| <br><br> This entry used one '''billion''' instead of one '''trillion''' for one of the ranges. <br><br>}} |
|||
This includes unit tests to demonstrate that 1000000145 **isn't** square-free. |
|||
See discussion. |
|||
<lang racket>#lang racket |
<lang racket>#lang racket |
||
Line 1,438: | Line 1,433: | ||
(print-list-to-80 (for/list ((n (in-range 1 (add1 145))) #:when (square-free? n)) n)) |
(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 # |
(print-list-to-80 (time (let ((table (not-square-free-set-for-range #e1e12 (add1 (+ #e1e12 145))))) |
||
(for/list ((n (in-range # |
(for/list ((n (in-range #e1e12 (add1 (+ #e1e12 145)))) |
||
#:when (square-free? n #:table table)) n)))) |
#:when (square-free? n #:table table)) n)))) |
||
(displayln "Compare time taken without the table (rather with table on the fly):") |
(displayln "Compare time taken without the table (rather with table on the fly):") |
||
(void (time (for/list ((n (in-range # |
(void (time (for/list ((n (in-range #e1e12 (add1 (+ #e1e12 145)))) #:when (square-free? n)) n))) |
||
(count-square-free-numbers 100) |
(count-square-free-numbers 100) |
||
Line 1,448: | Line 1,443: | ||
(count-square-free-numbers 10000) |
(count-square-free-numbers 10000) |
||
(count-square-free-numbers 100000) |
(count-square-free-numbers 100000) |
||
(count-square-free-numbers 1000000)) |
(count-square-free-numbers 1000000))</lang> |
||
(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}} |
{{out}} |
||
Line 1,463: | Line 1,451: | ||
91 93 94 95 97 101 102 103 105 106 107 109 110 111 113 114 115 118 119 122 123 |
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 |
127 129 130 131 133 134 137 138 139 141 142 143 145 |
||
cpu time: |
cpu time: 1969 real time: 1967 gc time: 876 |
||
1000000000001 1000000000002 1000000000003 1000000000005 1000000000006 |
|||
1000000001 1000000002 1000000003 1000000005 1000000006 1000000007 1000000009 |
|||
1000000000007 1000000000009 1000000000011 1000000000013 1000000000014 |
|||
1000000010 1000000011 1000000013 1000000014 1000000015 1000000018 1000000019 |
|||
1000000000015 1000000000018 1000000000019 1000000000021 1000000000022 |
|||
1000000021 1000000022 1000000027 1000000029 1000000030 1000000031 1000000033 |
|||
1000000000023 1000000000027 1000000000029 1000000000030 1000000000031 |
|||
1000000034 1000000037 1000000038 1000000039 1000000041 1000000042 1000000043 |
|||
1000000000033 1000000000037 1000000000038 1000000000039 1000000000041 |
|||
1000000045 1000000046 1000000047 1000000049 1000000051 1000000054 1000000055 |
|||
1000000000042 1000000000043 1000000000045 1000000000046 1000000000047 |
|||
1000000057 1000000058 1000000059 1000000061 1000000063 1000000065 1000000066 |
|||
1000000000049 1000000000051 1000000000054 1000000000055 1000000000057 |
|||
1000000067 1000000069 1000000070 1000000073 1000000074 1000000077 1000000078 |
|||
1000000000058 1000000000059 1000000000061 1000000000063 1000000000065 |
|||
1000000079 1000000081 1000000082 1000000083 1000000086 1000000087 1000000090 |
|||
1000000000066 1000000000067 1000000000069 1000000000070 1000000000073 |
|||
1000000091 1000000093 1000000094 1000000095 1000000097 1000000099 1000000101 |
|||
1000000000074 1000000000077 1000000000078 1000000000079 1000000000081 |
|||
1000000102 1000000103 1000000105 1000000106 1000000109 1000000110 1000000111 |
|||
1000000000082 1000000000085 1000000000086 1000000000087 1000000000090 |
|||
1000000113 1000000114 1000000115 1000000117 1000000118 1000000119 1000000121 |
|||
1000000000091 1000000000093 1000000000094 1000000000095 1000000000097 |
|||
1000000122 1000000123 1000000126 1000000127 1000000129 1000000130 1000000131 |
|||
1000000000099 1000000000101 1000000000102 1000000000103 1000000000105 |
|||
1000000133 1000000135 1000000137 1000000138 1000000139 1000000141 1000000142 |
|||
1000000000106 1000000000109 1000000000111 1000000000113 1000000000114 |
|||
1000000000115 1000000000117 1000000000118 1000000000119 1000000000121 |
|||
1000000000122 1000000000123 1000000000126 1000000000127 1000000000129 |
|||
1000000000130 1000000000133 1000000000135 1000000000137 1000000000138 |
|||
1000000000139 1000000000141 1000000000142 1000000000145 |
|||
Compare time taken without the table (rather with table on the fly): |
Compare time taken without the table (rather with table on the fly): |
||
cpu time: |
cpu time: 283469 real time: 285225 gc time: 118039 |
||
61 |
61 |
||
608 |
608 |