Square-free integers: Difference between revisions

=={{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>