Anonymous user
Square-free integers: Difference between revisions
Add Swift
m (→{{header|REXX}}: changed whitespace and comments, changed some variable names, used the correct glyph for a logical not.) |
(Add Swift) |
||
Line 1,893:
The number of square─free numbers between 1 and 10^6 (inclusive) is: 607926
</pre>
=={{header|Swift}}==
{{libheader|AttaSwift BigInt}}
<lang>import BigInt
import Foundation
extension BinaryInteger {
@inlinable
public var isSquare: Bool {
var x = self / 2
var seen = Set([x])
while x * x != self {
x = (x + (self / x)) / 2
if seen.contains(x) {
return false
}
seen.insert(x)
}
return true
}
@inlinable
public var isSquareFree: Bool {
return factors().dropFirst().reduce(true, { $0 && !$1.isSquare })
}
@inlinable
public func factors() -> [Self] {
let maxN = Self(Double(self).squareRoot())
var res = Set<Self>()
for factor in stride(from: 1, through: maxN, by: 1) where self % factor == 0 {
res.insert(factor)
res.insert(self / factor)
}
return res.sorted()
}
}
let sqFree1to145 = (1...145).filter({ $0.isSquareFree })
print("Square free numbers in range 1...145: \(sqFree1to145)")
let sqFreeBig = (BigInt(1_000_000_000_000)...BigInt(1_000_000_000_145)).filter({ $0.isSquareFree })
print("Square free numbers in range 1_000_000_000_000...1_000_000_000_045: \(sqFreeBig)")
var count = 0
for n in 1...1_000_000 {
if n.isSquareFree {
count += 1
}
switch n {
case 100, 1_000, 10_000, 100_000, 1_000_000:
print("Square free numbers between 1...\(n): \(count)")
case _:
break
}
}</lang>
{{out}}
<pre>Square free numbers in range 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]
Square free numbers in range 1_000_000_000_000...1_000_000_000_045: [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]
Square free numbers between 1...100: 61
Square free numbers between 1...1000: 608
Square free numbers between 1...10000: 6083
Square free numbers between 1...100000: 60794
Square free numbers between 1...1000000: 607926</pre>
=={{header|zkl}}==
| |||