Square-free integers: Difference between revisions
Content added Content deleted
(→{{header|J}}: arrayify the counting tasks) |
|||
Line 1,670: | Line 1,670: | ||
</pre> |
</pre> |
||
=={{header|Scala}}== |
|||
This example uses a brute-force approach to check whether a number is square-free, and builds a lazily evaluated list of all square-free numbers with a simple filter. To get the large square-free numbers, it avoids computing the beginning of the list by starting the list at a given number. |
|||
<lang scala>import spire.math.SafeLong |
|||
import spire.implicits._ |
|||
import scala.annotation.tailrec |
|||
object SquareFreeNums { |
|||
def main(args: Array[String]): Unit = { |
|||
println( |
|||
s"""|1 - 145: |
|||
|${formatTable(sqrFree.takeWhile(_ <= 145).toVector, 10)} |
|||
| |
|||
|1T - 1T+145: |
|||
|${formatTable(sqrFreeInit(1000000000000L).takeWhile(_ <= 1000000000145L).toVector, 6)} |
|||
| |
|||
|Square-Free Counts... |
|||
|100: ${sqrFree.takeWhile(_ <= 100).length} |
|||
|1000: ${sqrFree.takeWhile(_ <= 1000).length} |
|||
|10000: ${sqrFree.takeWhile(_ <= 10000).length} |
|||
|100000: ${sqrFree.takeWhile(_ <= 100000).length} |
|||
|1000000: ${sqrFree.takeWhile(_ <= 1000000).length} |
|||
|""".stripMargin) |
|||
} |
|||
def chkSqr(num: SafeLong): Boolean = !LazyList.iterate(SafeLong(2))(_ + 1).map(_.pow(2)).takeWhile(_ <= num).exists(num%_ == 0) |
|||
def sqrFreeInit(init: SafeLong): LazyList[SafeLong] = LazyList.iterate(init)(_ + 1).filter(chkSqr) |
|||
def sqrFree: LazyList[SafeLong] = sqrFreeInit(1) |
|||
def formatTable(lst: Vector[SafeLong], rlen: Int): String = { |
|||
@tailrec |
|||
def fHelper(ac: Vector[String], src: Vector[String]): String = { |
|||
if(src.nonEmpty) fHelper(ac :+ src.take(rlen).mkString, src.drop(rlen)) |
|||
else ac.mkString("\n") |
|||
} |
|||
val maxLen = lst.map(n => f"${n.toBigInt}%,d".length).max |
|||
val formatted = lst.map(n => s"%,${maxLen + 2}d".format(n.toBigInt)) |
|||
fHelper(Vector[String](), formatted) |
|||
} |
|||
}</lang> |
|||
{{out}} |
|||
<pre>1 - 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 |
|||
1T - 1T+145: |
|||
1,000,000,000,001 1,000,000,000,002 1,000,000,000,003 1,000,000,000,005 1,000,000,000,006 1,000,000,000,007 |
|||
1,000,000,000,009 1,000,000,000,011 1,000,000,000,013 1,000,000,000,014 1,000,000,000,015 1,000,000,000,018 |
|||
1,000,000,000,019 1,000,000,000,021 1,000,000,000,022 1,000,000,000,023 1,000,000,000,027 1,000,000,000,029 |
|||
1,000,000,000,030 1,000,000,000,031 1,000,000,000,033 1,000,000,000,037 1,000,000,000,038 1,000,000,000,039 |
|||
1,000,000,000,041 1,000,000,000,042 1,000,000,000,043 1,000,000,000,045 1,000,000,000,046 1,000,000,000,047 |
|||
1,000,000,000,049 1,000,000,000,051 1,000,000,000,054 1,000,000,000,055 1,000,000,000,057 1,000,000,000,058 |
|||
1,000,000,000,059 1,000,000,000,061 1,000,000,000,063 1,000,000,000,065 1,000,000,000,066 1,000,000,000,067 |
|||
1,000,000,000,069 1,000,000,000,070 1,000,000,000,073 1,000,000,000,074 1,000,000,000,077 1,000,000,000,078 |
|||
1,000,000,000,079 1,000,000,000,081 1,000,000,000,082 1,000,000,000,085 1,000,000,000,086 1,000,000,000,087 |
|||
1,000,000,000,090 1,000,000,000,091 1,000,000,000,093 1,000,000,000,094 1,000,000,000,095 1,000,000,000,097 |
|||
1,000,000,000,099 1,000,000,000,101 1,000,000,000,102 1,000,000,000,103 1,000,000,000,105 1,000,000,000,106 |
|||
1,000,000,000,109 1,000,000,000,111 1,000,000,000,113 1,000,000,000,114 1,000,000,000,115 1,000,000,000,117 |
|||
1,000,000,000,118 1,000,000,000,119 1,000,000,000,121 1,000,000,000,122 1,000,000,000,123 1,000,000,000,126 |
|||
1,000,000,000,127 1,000,000,000,129 1,000,000,000,130 1,000,000,000,133 1,000,000,000,135 1,000,000,000,137 |
|||
1,000,000,000,138 1,000,000,000,139 1,000,000,000,141 1,000,000,000,142 1,000,000,000,145 |
|||
Square-Free Counts... |
|||
100: 61 |
|||
1000: 608 |
|||
10000: 6083 |
|||
100000: 60794 |
|||
1000000: 607926</pre> |
|||
=={{header|Sidef}}== |
=={{header|Sidef}}== |