Square-free integers: Difference between revisions

{{trans|Python}}

V max = Int(sqrt(_number))

ListSquareFrees(1, 100)

{{out}}

=={{header|ALGOL 68}}==

# count/show some square free numbers #

# a number is square free if not divisible by any square and so not divisible #

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 ) )

{{out}}

<pre>Square free numbers from 1 to 145

=={{header|AWK}}==

# syntax: GAWK -f SQUARE-FREE_INTEGERS.AWK

# converted from LUA

return(1)

}

{{out}}

<pre>

=={{header|C}}==

{{trans|Go}}

#include <stdlib.h>

#include <math.h>

free(sf);

return 0;

{{out}}

=={{header|C++}}==

#include <iostream>

#include <string>

print_square_free_count(1, 1000000);

return 0;

{{out}}

=={{header|D}}==

{{trans|Java}}

import std.math;

import std.stdio;

writefln(" from 1 to %d = %d", to, squareFree(1, to).length);

}

{{out}}

<pre>Square-free integers from 1 to 145:

For instance, the prime factorization of <tt>12</tt> is <code>2 * 2 * 3</code>, or in other words, <code>2² * 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

1 145 10 12 ^ dup 145 + [ sq-free-show ] 2bi@ ! part 1

{{out}}

<pre>

=={{header|Forth}}==

dup 4 mod 0= if drop false exit then

3

main

{{out}}

=={{header|FreeBASIC}}==

' compile with: fbc -s console

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre> 1 2 3 5 6 7 10 11 13 14 15 17 19 21 22 23 26 29 30 31

=={{header|Go}}==

import (

fmt.Printf(" from %d to %d = %d\n", 1, n, len(squareFree(1, n)))

}

{{out}}

=={{header|Haskell}}==

import Math.NumberTheory.Primes (factorise)

import Text.Printf (printf)

printSquareFrees 20 1 145

printSquareFrees 5 1000000000000 1000000000145

{{out}}

=={{header|J}}==

'''Solution:'''

filter=: adverb def ' #~ u' NB. filter right arg using verb to left

countSqrFree=: +/@:isSqrFree

'''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

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

=={{header|Java}}==

{{trans|Go}}

import java.util.List;

}

}

{{out}}

=={{header|Julia}}==

const maxrootprime = Int64(floor(sqrt(1000000000145)))

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

=={{header|Kotlin}}==

{{trans|Go}}

import kotlin.math.sqrt

j -> println(" from 1 to $j = ${squareFree(1..j).size}")

}

{{out}}

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

{1, 1000000}

}

{{out}}

<pre>From 1 to 145:

=={{header|Maple}}==

with(NumberTheory):

with(ArrayTools):

seq(cat(sfgroups[i], " from 1 to ", 10^(i+1)), i = 1..5);

{{out}}<pre>

[1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30, 31, 33,

=={{header|Mathematica}}/{{header|Wolfram Language}}==

findSquareFree[n__] := Select[Range[n], squareFree];

findSquareFree[45]

findSquareFree[10^9, 10^9 + 145]

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

=={{header|Nanoquery}}==

{{trans|AWK}}

if n < 2^2

return true

square_free(1, 10000, false)

square_free(1, 100000, false)

{{out}}

<pre>

=={{header|Nim}}==

{{trans|Go}}

echo "\nNumber of square-free integers:\n"

for n in [100, 1_000, 10_000, 100_000, 1_000_000]:

{{out}}

</pre>

=={{header|OCaml}}==

let squarefree (number: int) : bool =

let max = Float.of_int number |> sqrt |> Float.to_int |> (fun x -> x + 2) in

print_squarefree_integers (1000000000000, 1000000000146)

;;

{{out}}

{{works with|Free Pascal}}

As so often, marking/sieving multiples of square of primes to speed things up.

{$IFDEF FPC}

{$MODE DELPHI}

Count_x10;

{{out}}

<pre style="height:35ex">Square free numbers from 1 to 145

=={{header|Perl}}==

{{libheader|ntheory}}

sub square_free_count {

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>

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

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

=={{header|Python}}==

import math

ListSquareFrees( 1, 100 )

ListSquareFrees( 1000000000000, 1000000000145 )

'''Output:'''

=={{header|Racket}}==

(define (not-square-free-set-for-range range-min (range-max (add1 range-min)))

(count-square-free-numbers 10000)

(count-square-free-numbers 100000)

{{out}}

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.

sub prime-factors ( Int $n where * > 0 ) {

return $n if $n.is-prime;

say "\nThe number of square─free numbers between 1 and {$_} (inclusive) is: ",

+(1 .. .Int).race.grep: &is-square-free;

{{out}}

<pre>

=={{header|REXX}}==

numeric digits 20 /*be able to handle larger numbers. */

parse arg LO HI . /*obtain optional arguments from the CL*/

if _>=0 then do; x= _; r= r + q; end

end /*while q>1*/

This REXX program makes use of &nbsp; '''linesize''' &nbsp; REXX program (or BIF) &nbsp; which is used to determine the screen width (or linesize) of the terminal (console); &nbsp; not all REXXes have this BIF.

=={{header|Ruby}}==

class Integer

puts "#{count} square-frees upto #{n}" if markers.include?(n)

end

{{out}}

<pre>1 2 3 5 6 7 10 11 13 14 15 17 19 21 22 23 26 29 30 31

=={{header|Rust}}==

{{trans|C++}}

if n & 3 == 0 {

return false;

n *= 10;

}

{{out}}

</pre>

===Rust FP===

fn iter(x: usize, start: usize, prev: usize) -> bool {

let limit = (x as f64).sqrt().ceil() as usize;

limit, number, duration)

}

{{out}}

<pre>square_free numbers between 1 and 145:

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

fHelper(Vector[String](), formatted)

}

{{out}}

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)

var c = square_free_count(10**n)

say "The number of square─free numbers between 1 and 10^#{n} (inclusive) is: #{c}"

{{out}}

{{libheader|AttaSwift BigInt}}

import Foundation

break

}

{{out}}

=={{header|Tcl}}==

for {set d 2} {($d * $d) <= $n} {set d [expr {($d+1)|1}]} {

if {0 == ($n % $d)} {

showCount 1 $H

}

{{out}}

<pre>Square-free integers in range 1..145 are:

=={{header|Visual Basic .NET}}==

{{trans|D}}

Function Sieve(limit As Long) As List(Of Long)

End Sub

{{out}}

<pre>Square-free integers from 1 to 145:

=={{header|Wren}}==

{{libheader|Wren-fmt}}

var isSquareFree = Fn.new { |n|

}

System.print(count)

{{out}}

=={{header|zkl}}==

var [const]

BI=Import.lib("zklBigNum"), // GNU Multiple Precision Arithmetic Library

}

return(cnt,sink.close());

squareFree(1,145,True)[1].pump(Console.println,

T(Void.Read,14,False),fcn{ vm.arglist.apply("%4d ".fmt).concat() });

println("\nSquare-free integers from 1000000000000 to 1000000000145:");

squareFree(1000000000000,1000000000145,True)[1].pump(Console.println,

{{out}}

<pre style="height:35ex">

</pre>

squareFree(1,n)[0]:

println("%,9d square-free integers from 1 to %,d".fmt(_,n));

n*=10;

{{out}}

<pre>