Square-free integers: Difference between revisions

From Rosetta Code
Content added Content deleted
(→‎{{header|Perl 6}}: Add a Perl 6 example)
m (→‎{{header|Perl 6}}: More efficient counting sub. If we're only counting, don't need them in order)
Line 202: Line 202:
for 1e2, 1e3, 1e4, 1e5, 1e6 {
for 1e2, 1e3, 1e4, 1e5, 1e6 {
say "\nThe number of square─free numbers between 1 and {$_} (inclusive) is: ",
say "\nThe number of square─free numbers between 1 and {$_} (inclusive) is: ",
+(1 .. .Int).hyper(:4batch).map({ $_ if .&is-square-free }).list;
+(1 .. .Int).race.map: { 1 if .&is-square-free };
}</lang>
}</lang>
{{out}}
{{out}}

Revision as of 23:27, 2 July 2018

Square-free integers is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
Task

Write a function to test if a number is   square-free.


A   square-free   is an integer which is divisible by no perfect square other than   1   (unity).

For this task, only positive square-free numbers will be used.


Show here (on this page) all square-free integers (in a horizontal format) that are between:

  •   1   ───►   145     (inclusive)
  •   1 trillion   ───►   1 trillion + 145     (inclusive)


(One trillion = 1,000,000,000,000)


Show here (on this page) the count of square-free integers from:

  •   1   ───►   one hundred     (inclusive)
  •   1   ───►   one thousand     (inclusive)
  •   1   ───►   ten thousand     (inclusive)
  •   1   ───►   one hundred thousand     (inclusive)
  •   1   ───►   one million     (inclusive)


See also



Go

<lang go>package main

import (

   "fmt"
   "math"

)

func sieve(limit uint64) (primes []uint64) {

   c := make([]bool, limit+1) // composite = true
   c[2] = false
   for i := uint64(4); i <= limit; i += 2 {
       c[i] = true
   }
   p := uint64(3)
   for {
       p2 := p * p
       if p2 > limit {
           break
       }
       for i := p2; i <= limit; i += p {
           c[i] = true
       }
       for {
           p += 2
           if !c[p] {
               break
           }
       }
   }
   for i := uint64(2); i <= limit; i++ {
       if !c[i] {
           primes = append(primes, i)
       }
   }
   return

}

func squareFree(from, to uint64) (results []uint64) {

   limit := uint64(math.Sqrt(float64(to)))
   primes := sieve(limit)

outer:

   for i := from; i <= to; i++ {
       for _, p := range primes {
           p2 := p * p
           if p2 > i {
               break
           }
           if i%p2 == 0 {
               continue outer
           }
       }
       results = append(results, i)
   }
   return

}

const trillion uint64 = 1000000000000

func main() {

   fmt.Println("Square-free integers from 1 to 145:")
   sf := squareFree(1, 145)
   for i := 0; i < len(sf); i++ {
       if i > 0 && i%20 == 0 {
           fmt.Println()
       }
       fmt.Printf("%4d", sf[i])
   }
   fmt.Printf("\n\nSquare-free integers from %d to %d:\n", trillion, trillion+145)
   sf = squareFree(trillion, trillion+145)
   for i := 0; i < len(sf); i++ {
       if i > 0 && i%5 == 0 {
           fmt.Println()
       }
       fmt.Printf("%14d", sf[i])
   }
   fmt.Println("\n\nNumber of square-free integers:\n")
   fmt.Printf("  from %d to %d = %d\n", 1, 100, len(squareFree(1, 100)))
   fmt.Printf("  from %d to %d = %d\n", 1, 1000, len(squareFree(1, 1000)))
   fmt.Printf("  from %d to %d = %d\n", 1, 10000, len(squareFree(1, 10000)))
   fmt.Printf("  from %d to %d = %d\n", 1, 100000, len(squareFree(1, 100000)))
   fmt.Printf("  from %d to %d = %d\n", 1, 1000000, len(squareFree(1, 1000000)))

}</lang>

Output:
Square-free integers from 1 to 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 integers from 1000000000000 to 1000000000145:
 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

Number of square-free integers:

  from 1 to 100 = 61
  from 1 to 1000 = 608
  from 1 to 10000 = 6083
  from 1 to 100000 = 60794
  from 1 to 1000000 = 607926

Perl 6

Works with: Rakudo version 2018.06

<lang perl6># Prime factorization routines sub prime-factors ( Int $n where * > 0 ) {

   return $n if $n.is-prime;
   return [] if $n == 1;
   my $factor = find-factor( $n );
   sort flat prime-factors( $factor ), prime-factors( $n div $factor );

}

sub find-factor ( Int $n, $constant = 1 ) {

   my $x      = 2;
   my $rho    = 1;
   my $factor = 1;
   while $factor == 1 {
       $rho *= 2;
       my $fixed = $x;
       for ^$rho {
           $x = ( $x * $x + $constant ) % $n;
           $factor = ( $x - $fixed ) gcd $n;
           last if 1 < $factor;
       }
   }
   $factor = find-factor( $n, $constant + 1 ) if $n == $factor;
   $factor;

}

  1. Task routines

multi is-square-free (Int $n) { $n.&prime-factors.Bag.max(*.value).value > 1 ?? False !! True } multi is-square-free (1) { True }

  1. The Task
  1. Part 1

say "Square─free numbers between 1 and 145:"; say (1..145).map({ $_ if .&is-square-free }).list.fmt("%3d").comb(100).join("\n");

  1. Part 2

say "\nSquare─free numbers between 1000000000000 and 1000000000145:"; say (1000000000000..1000000000145).hyper(:4batch).map({ $_ if .&is-square-free }).list.comb(98).join("\n");

  1. Part 3

for 1e2, 1e3, 1e4, 1e5, 1e6 {

   say "\nThe number of square─free numbers between 1 and {$_} (inclusive) is: ",
   +(1 .. .Int).race.map: { 1 if .&is-square-free };

}</lang>

Output:
Square─free numbers between  1  and 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 between 1000000000000 and 1000000000145:
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

The number of square─free numbers between 1 and 100 (inclusive) is: 61

The number of square─free numbers between 1 and 1000 (inclusive) is: 608

The number of square─free numbers between 1 and 10000 (inclusive) is: 6083

The number of square─free numbers between 1 and 100000 (inclusive) is: 60794

The number of square─free numbers between 1 and 1000000 (inclusive) is: 607926

REXX

<lang rexx>/*REXX program displays square─free numbers (integers > 1) up to a specified limit. */ numeric digits 20 parse arg LO HI . /*obtain optional arguments from the CL*/ if LO== | LO=="," then LO= 1 /*Not specified? Then use the default.*/ if HI== | HI=="," then HI=145 /* " " " " " " */ sw= linesize() - 1 /*use one less than a full line. */ count = 0 /*count of square─free numbers found. */ $= /*variable that holds a line of numbers*/

  do j=LO  to abs(HI)                           /*process all integers between LO & HI.*/
  if \isSquareFree(j)   then iterate            /*Not square─free?   Then skip this #. */
  count= count + 1                              /*bump the count of square─free numbers*/
  if HI<0  then iterate                         /*Only counting 'em? Then look for more*/
  if length($ || j)<sw  then $= strip($ j)      /*append the number to the output list.*/
                        else do;  say $;  $=j;  end        /*display a line of numbers.*/
  end   /*j*/

TheNum= 'The number of square─free numbers between ' if HI<0 then say TheNum LO " and " abs(HI) ' (inclusive) is: ' count if $\== then say $ /*are there any residuals to display ? */ exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ isSquareFree: procedure; parse arg #; if #<1 then return 0 /*is the number too small?*/

             limit= iSqrt(#)                    /*obtain the integer square root of #.?*/
             odd=#//2                           /*ODD=1   if # is odd,   ODD=0 if even.*/
                      do k=2+odd  to limit  by 1+odd    /*use all numbers, or just odds*/
                      if # // k**2 == 0  then return 0  /*Is # divisible by a square?  */
                      end   /*k*/                       /* [↑]  Yes? Then ^ square─free*/
             return 1

/*──────────────────────────────────────────────────────────────────────────────────────*/ iSqrt: procedure; parse arg x; r=0; q=1; do while q<=x; q=q*4; end

                 do while q>1; q=q%4; _=x-r-q; r=r%2; if _>=0 then do;x=_;r=r+q; end; end
      return r                                  /*R  is the integer square root of  X. */</lang>

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.

The   LINESIZE.REX   REXX program is included here   ──►   LINESIZE.REX.


output   when using the default input:

(Shown at three-quarter size.)

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
output   when using the input of:     1000000000000   1000000000145

(Shown at three-quarter size.)

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

{{out|output|text=  when using the (separate runs) inputs of:     1   -100   (and others)

The number of square─free numbers between  1  and  100  (inclusive)  is:  61

The number of square─free numbers between  1  and  1000  (inclusive)  is:  608

The number of square─free numbers between  1  and  10000  (inclusive)  is:  6083

The number of square─free numbers between  1  and  100000  (inclusive)  is:  60794

The number of square─free numbers between  1  and  1000000  (inclusive)  is:  607926