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 #e1e9 (add1 (+ #e1e9 145)))))
(print-list-to-80 (time (let ((table (not-square-free-set-for-range #e1e12 (add1 (+ #e1e12 145)))))
(for/list ((n (in-range #e1e9 (add1 (+ #e1e9 145))))
(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 #e1e9 (add1 (+ #e1e9 145)))) #:when (square-free? n)) n)))
(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: 47 real time: 45 gc time: 15
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: 7781 real time: 7865 gc time: 1955
cpu time: 283469 real time: 285225 gc time: 118039
61
61
608
608
Retrieved from "https://rosettacode.org/wiki/Square-free_integers"