Square-free integers: Difference between revisions
m
syntax highlighting fixup automation
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
|||
Line 35:
{{trans|Python}}
<
V max = Int(sqrt(_number))
Line 56:
ListSquareFrees(1, 100)
ListSquareFrees(1000000000000, 1000000000145)</
{{out}}
Line 98:
=={{header|ALGOL 68}}==
<
# count/show some square free numbers #
# a number is square free if not divisible by any square and so not divisible #
Line 179:
INT sf 1 000 000 := sf 100 000 + count square free( 100 001, 1 000 000 );
print( ( "square free numbers between 1 and 1 000 000: ", whole( sf 1 000 000, -6 ), newline ) )
END</
{{out}}
<pre>Square free numbers from 1 to 145
Line 213:
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f SQUARE-FREE_INTEGERS.AWK
# converted from LUA
Line 252:
return(1)
}
</syntaxhighlight>
{{out}}
<pre>
Line 285:
=={{header|C}}==
{{trans|Go}}
<
#include <stdlib.h>
#include <math.h>
Line 371:
free(sf);
return 0;
}</
{{out}}
Line 411:
=={{header|C++}}==
<
#include <iostream>
#include <string>
Line 468:
print_square_free_count(1, 1000000);
return 0;
}</
{{out}}
Line 502:
=={{header|D}}==
{{trans|Java}}
<
import std.math;
import std.stdio;
Line 580:
writefln(" from 1 to %d = %d", to, squareFree(1, to).length);
}
}</
{{out}}
<pre>Square-free integers from 1 to 145:
Line 620:
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.
<
math.primes.factors math.ranges sequences sets ;
IN: rosetta-code.square-free
Line 639:
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</
{{out}}
<pre>
Line 677:
=={{header|Forth}}==
<
dup 4 mod 0= if drop false exit then
3
Line 733:
main
bye</
{{out}}
Line 773:
=={{header|FreeBASIC}}==
<
' compile with: fbc -s console
Line 861:
Print : Print "hit any key to end program"
Sleep
End</
{{out}}
<pre> 1 2 3 5 6 7 10 11 13 14 15 17 19 21 22 23 26 29 30 31
Line 895:
=={{header|Go}}==
<
import (
Line 975:
fmt.Printf(" from %d to %d = %d\n", 1, n, len(squareFree(1, n)))
}
}</
{{out}}
Line 1,016:
=={{header|Haskell}}==
<
import Math.NumberTheory.Primes (factorise)
import Text.Printf (printf)
Line 1,056:
printSquareFrees 20 1 145
printSquareFrees 5 1000000000000 1000000000145
printSquareFreeCounts [100, 1000, 10000, 100000, 1000000] 1 1000000</
{{out}}
Line 1,097:
=={{header|J}}==
'''Solution:'''
<
filter=: adverb def ' #~ u' NB. filter right arg using verb to left
countSqrFree=: +/@:isSqrFree
thru=: <. + i.@(+ *)@-~ NB. helper verb</
'''Required Examples:'''
<
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...
100 list isSqrFree filter 1000000000000 thru 1000000000145 NB. ensure that all results are displayed
Line 1,124:
608
1 countSqrFree@thru&> 10 ^ 2 3 4 5 6 NB. count square free ints for 1 to each of 100, 1000, 10000, 10000, 100000 and 1000000
61 608 6083 60794 607926</
=={{header|Java}}==
{{trans|Go}}
<
import java.util.List;
Line 1,196:
}
}
}</
{{out}}
Line 1,356:
=={{header|Julia}}==
<
const maxrootprime = Int64(floor(sqrt(1000000000145)))
Line 1,399:
squarefreebetween(1000000000000, 1000000000145)
squarefreecount([100, 1000, 10000, 100000], 1000000)
</
The squarefree numbers between 1 and 145 are:
1 2 3 5 6 7 10 11 13 14 15 17 19 21 22 23
Line 1,435:
=={{header|Kotlin}}==
{{trans|Go}}
<
import kotlin.math.sqrt
Line 1,490:
j -> println(" from 1 to $j = ${squareFree(1..j).size}")
}
}</
{{out}}
Line 1,532:
=={{header|Lua}}==
This is a naive method, runs in about 1 second on LuaJIT.
<
for root = 2, math.sqrt(n) do
if n % (root * root) == 0 then return false end
Line 1,564:
{1, 1000000}
}
for _, example in pairs(testCases) do run(unpack(example)) end</
{{out}}
<pre>From 1 to 145:
Line 1,606:
=={{header|Maple}}==
<syntaxhighlight lang="maple">
with(NumberTheory):
with(ArrayTools):
Line 1,648:
seq(cat(sfgroups[i], " from 1 to ", 10^(i+1)), i = 1..5);
</syntaxhighlight>
{{out}}<pre>
[1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30, 31, 33,
Line 1,705:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
findSquareFree[n__] := Select[Range[n], squareFree];
findSquareFree[45]
findSquareFree[10^9, 10^9 + 145]
Length[findSquareFree[10^6]]</
{{out}}
<pre>{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}
Line 1,736:
=={{header|Nanoquery}}==
{{trans|AWK}}
<
if n < 2^2
return true
Line 1,775:
square_free(1, 10000, false)
square_free(1, 100000, false)
square_free(1, 1000000, false)</
{{out}}
<pre>
Line 1,808:
=={{header|Nim}}==
{{trans|Go}}
<
Line 1,863:
echo "\nNumber of square-free integers:\n"
for n in [100, 1_000, 10_000, 100_000, 1_000_000]:
echo " from $1 to $2 = $3".format(1, n, squareFree(1, n).len)</
{{out}}
Line 1,903:
</pre>
=={{header|OCaml}}==
<
let squarefree (number: int) : bool =
let max = Float.of_int number |> sqrt |> Float.to_int |> (fun x -> x + 2) in
Line 1,939:
print_squarefree_integers (1000000000000, 1000000000146)
;;
</syntaxhighlight>
{{out}}
Line 1,989:
{{works with|Free Pascal}}
As so often, marking/sieving multiples of square of primes to speed things up.
<
{$IFDEF FPC}
{$MODE DELPHI}
Line 2,150:
Count_x10;
end.</
{{out}}
<pre style="height:35ex">Square free numbers from 1 to 145
Line 2,201:
=={{header|Perl}}==
{{libheader|ntheory}}
<
sub square_free_count {
Line 2,222:
my $c = square_free_count(10**$n);
print "The number of square-free numbers between 1 and 10^$n (inclusive) is: $c\n";
}</
{{out}}
<pre>
Line 2,239:
=={{header|Phix}}==
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">square_frees</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">start</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">finish</span><span style="color: #0000FF;">)</span>
Line 2,267:
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" from %,d to %,d = %,d\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">lim</span><span style="color: #0000FF;">,</span><span style="color: #000000;">len</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</
{{out}}
<pre>
Line 2,306:
=={{header|Python}}==
<syntaxhighlight lang="python">
import math
Line 2,329:
ListSquareFrees( 1, 100 )
ListSquareFrees( 1000000000000, 1000000000145 )
</syntaxhighlight>
'''Output:'''
Line 2,366:
=={{header|Racket}}==
<
(define (not-square-free-set-for-range range-min (range-max (add1 range-min)))
Line 2,408:
(count-square-free-numbers 10000)
(count-square-free-numbers 100000)
(count-square-free-numbers 1000000))</
{{out}}
Line 2,448:
The prime factoring algorithm is not really the best option for finding long runs of sequential square-free numbers. It works, but is probably better suited for testing arbitrary numbers rather than testing every sequential number from 1 to some limit. If you know that that is going to be your use case, there are faster algorithms.
<syntaxhighlight lang="raku"
sub prime-factors ( Int $n where * > 0 ) {
return $n if $n.is-prime;
Line 2,491:
say "\nThe number of square─free numbers between 1 and {$_} (inclusive) is: ",
+(1 .. .Int).race.grep: &is-square-free;
}</
{{out}}
<pre>
Line 2,529:
=={{header|REXX}}==
<
numeric digits 20 /*be able to handle larger numbers. */
parse arg LO HI . /*obtain optional arguments from the CL*/
Line 2,563:
if _>=0 then do; x= _; r= r + q; end
end /*while q>1*/
return r /*R is the integer square root of X. */</
This REXX program makes use of '''linesize''' REXX program (or BIF) which is used to determine the screen width (or linesize) of the terminal (console); not all REXXes have this BIF.
Line 2,604:
=={{header|Ruby}}==
<
class Integer
Line 2,625:
puts "#{count} square-frees upto #{n}" if markers.include?(n)
end
</syntaxhighlight>
{{out}}
<pre>1 2 3 5 6 7 10 11 13 14 15 17 19 21 22 23 26 29 30 31
Line 2,659:
=={{header|Rust}}==
{{trans|C++}}
<
if n & 3 == 0 {
return false;
Line 2,719:
n *= 10;
}
}</
{{out}}
Line 2,751:
</pre>
===Rust FP===
<
fn iter(x: usize, start: usize, prev: usize) -> bool {
let limit = (x as f64).sqrt().ceil() as usize;
Line 2,781:
limit, number, duration)
}
}</
{{out}}
<pre>square_free numbers between 1 and 145:
Line 2,815:
=={{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.
<
import spire.implicits._
Line 2,854:
fHelper(Vector[String](), formatted)
}
}</
{{out}}
Line 2,895:
In Sidef, the functions ''is_square_free(n)'' and ''square_free_count(min, max)'' are built-in. However, we can very easily reimplement them in Sidef code, as fast integer factorization methods are also available in the language.
<
n.abs! if (n < 0)
Line 2,928:
var c = square_free_count(10**n)
say "The number of square─free numbers between 1 and 10^#{n} (inclusive) is: #{c}"
}</
{{out}}
Line 2,971:
{{libheader|AttaSwift BigInt}}
<syntaxhighlight lang="text">import BigInt
import Foundation
Line 3,033:
break
}
}</
{{out}}
Line 3,046:
=={{header|Tcl}}==
<
for {set d 2} {($d * $d) <= $n} {set d [expr {($d+1)|1}]} {
if {0 == ($n % $d)} {
Line 3,103:
showCount 1 $H
}
</syntaxhighlight>
{{out}}
<pre>Square-free integers in range 1..145 are:
Line 3,138:
=={{header|Visual Basic .NET}}==
{{trans|D}}
<
Function Sieve(limit As Long) As List(Of Long)
Line 3,224:
End Sub
End Module</
{{out}}
<pre>Square-free integers from 1 to 145:
Line 3,262:
=={{header|Wren}}==
{{libheader|Wren-fmt}}
<
var isSquareFree = Fn.new { |n|
Line 3,295:
}
System.print(count)
}</
{{out}}
Line 3,335:
=={{header|zkl}}==
<
var [const]
BI=Import.lib("zklBigNum"), // GNU Multiple Precision Arithmetic Library
Line 3,355:
}
return(cnt,sink.close());
}</
<
squareFree(1,145,True)[1].pump(Console.println,
T(Void.Read,14,False),fcn{ vm.arglist.apply("%4d ".fmt).concat() });
Line 3,362:
println("\nSquare-free integers from 1000000000000 to 1000000000145:");
squareFree(1000000000000,1000000000145,True)[1].pump(Console.println,
T(Void.Read,4,False),fcn{ vm.arglist.concat(" ") });</
{{out}}
<pre style="height:35ex">
Line 3,394:
</pre>
<
squareFree(1,n)[0]:
println("%,9d square-free integers from 1 to %,d".fmt(_,n));
n*=10;
}</
{{out}}
<pre>
|