Square-free integers: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (→{{header|Perl 6}}: More efficient counting sub. If we're only counting, don't need them in order) |
(added Factor) |
||
Line 31: | Line 31: | ||
:* the Wikipedia entry: [https://wikipedia.org/wiki/Square-free_integer square-free integer] |
:* the Wikipedia entry: [https://wikipedia.org/wiki/Square-free_integer square-free integer] |
||
<br><br> |
<br><br> |
||
=={{header|Factor}}== |
|||
The <code>sq-free?</code> word merits some explanation. Per the Wikipedia entry on square-free integers, <q cite="https://en.wikipedia.org/wiki/Square-free_integer#Equivalent_characterizations">A positive integer <i>n</i> is square-free if and only if in the prime factorization of <i>n</i>, no prime factor occurs with an exponent larger than one.</q> |
|||
For instance, the prime factorization of <tt>12</tt> is <code>2 * 2 * 3</code>, or in other words, <code>2<sup>2</sup> * 3</code>. The <tt>2</tt> repeats, so we know <tt>12</tt> isn't square-free. |
|||
<lang factor>USING: formatting grouping io kernel math math.functions |
|||
math.primes.factors math.ranges sequences sets ; |
|||
IN: rosetta-code.square-free |
|||
: sq-free? ( n -- ? ) factors all-unique? ; |
|||
! Word wrap for numbers. |
|||
: numbers-per-line ( m -- n ) log10 >integer 2 + 80 swap /i ; |
|||
: sq-free-show ( from to -- ) |
|||
2dup "Square-free integers from %d to %d:\n" printf |
|||
[ [a,b] [ sq-free? ] filter ] [ numbers-per-line group ] bi |
|||
[ [ "%3d " printf ] each nl ] each nl ; |
|||
: sq-free-count ( limit -- ) |
|||
dup [1,b] [ sq-free? ] count swap |
|||
"%6d square-free integers from 1 to %d\n" printf ; |
|||
1 145 10 12 ^ dup 145 + [ sq-free-show ] 2bi@ ! part 1 |
|||
2 6 [a,b] [ 10 swap ^ ] map [ sq-free-count ] each ! part 2</lang> |
|||
{{out}} |
|||
<pre> |
|||
Square-free integers from 1 to 145: |
|||
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 |
|||
Square-free integers from 1000000000000 to 1000000000145: |
|||
1000000000001 1000000000002 1000000000003 1000000000005 1000000000006 |
|||
1000000000007 1000000000009 1000000000011 1000000000013 1000000000014 |
|||
1000000000015 1000000000018 1000000000019 1000000000021 1000000000022 |
|||
1000000000023 1000000000027 1000000000029 1000000000030 1000000000031 |
|||
1000000000033 1000000000037 1000000000038 1000000000039 1000000000041 |
|||
1000000000042 1000000000043 1000000000045 1000000000046 1000000000047 |
|||
1000000000049 1000000000051 1000000000054 1000000000055 1000000000057 |
|||
1000000000058 1000000000059 1000000000061 1000000000063 1000000000065 |
|||
1000000000066 1000000000067 1000000000069 1000000000070 1000000000073 |
|||
1000000000074 1000000000077 1000000000078 1000000000079 1000000000081 |
|||
1000000000082 1000000000085 1000000000086 1000000000087 1000000000090 |
|||
1000000000091 1000000000093 1000000000094 1000000000095 1000000000097 |
|||
1000000000099 1000000000101 1000000000102 1000000000103 1000000000105 |
|||
1000000000106 1000000000109 1000000000111 1000000000113 1000000000114 |
|||
1000000000115 1000000000117 1000000000118 1000000000119 1000000000121 |
|||
1000000000122 1000000000123 1000000000126 1000000000127 1000000000129 |
|||
1000000000130 1000000000133 1000000000135 1000000000137 1000000000138 |
|||
1000000000139 1000000000141 1000000000142 1000000000145 |
|||
61 square-free integers from 1 to 100 |
|||
608 square-free integers from 1 to 1000 |
|||
6083 square-free integers from 1 to 10000 |
|||
60794 square-free integers from 1 to 100000 |
|||
607926 square-free integers from 1 to 1000000 |
|||
</pre> |
|||
=={{header|Go}}== |
=={{header|Go}}== |