N-smooth numbers: Difference between revisions

'''n-smooth''' &nbsp; numbers are positive integers which have no prime factors <big> &gt; </big> '''n'''.

 

<br>there are &nbsp; <u>no</u> &nbsp; '''9-smooth''' numbers.

 

 

<br>2-smooth &nbsp; numbers are non-negative powers of two.

 

 

 

;Task:

 

 

:* &nbsp; Wikipedia entry: &nbsp; [[wp:Hamming numbers|Hamming numbers]] &nbsp; &nbsp; (this link is re-directed to &nbsp; '''Regular number''').

:* &nbsp; Wikipedia entry: &nbsp; [[wp:Smooth number|Smooth number]]

<br><br>

 

=={{header|C}}==

{{libheader|GMP}}

#include <stdint.h>

#include <stdio.h>

}

return 0;

 

{{out}}

{{trans|D}}

The output for the 30,000 3-smooth numbers is not correct due to insuffiant bits to represent that actual value

#include <iostream>

#include <vector>

 

return 0;

{{out}}

<pre>The first 2-smooth numbers are:

=={{header|C sharp|C#}}==

{{trans|D}}

using System.Collections.Generic;

using System.Linq;

}

}

{{out}}

<pre>The first 2-smooth numbers are:

=={{header|Crystal}}==

{{trans|Ruby}}

 

end

true

print nsmooth(prime, 30019)[29999..]

puts

 

{{out}}

=={{header|D}}==

{{trans|Kotlin}}

import std.bigint;

import std.exception;

writeln;

}

{{out}}

<pre>The first 2-smooth numbers are:

{{libheader| Velthuis.BigIntegers}}Thanks for Rudy Velthuis[https://github.com/rvelthuis/DelphiBigNumbers]

{{Trans|D}}

program N_smooth_numbers;

 

Readln;

end.

 

=={{header|Factor}}==

math.order math.primes math.text.english namespaces prettyprint

sequences tools.memory.private ;

503 521 30,000 30,019 show-smooth ;

 

{{out}}

<pre>

 

=={{header|Go}}==

 

import (

fmt.Println(nSmooth(i, 30019)[29999:], "\n")

}

 

{{out}}

The solution is based on the hamming numbers solution [[Hamming_numbers#Avoiding_generation_of_duplicates]].<br>

Uses Library Data.Number.Primes: http://hackage.haskell.org/package/primes-0.2.1.0/docs/Data-Numbers-Primes.html

import Text.Printf (printf)

 

showTwentyFive = show . take 25 . nSmooth

showRange1 = show . ((<$> [2999 .. 3001]) . (!!) . nSmooth)

{{out}}

<pre>

=={{header|J}}==

This solution involves sorting, duplicate removal, and limits on the number of preserved terms.

nsmooth=: dyad define NB. TALLY nsmooth N

factors=. x: i.@:>:&.:(p:inv) y

end.

)

25 (] ; nsmooth)&> p: i. 10

┌──┬────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐

 

=={{header|Java}}==

import java.math.BigInteger;

import java.util.ArrayList;

 

}

 

{{out}}

The 30000 through 30019 521-smooth numbers:

62287 62288 62291 62292 62300 62304 62307 62308 62310 62315 62320 62321 62322 62325 62328 62329 62330 62331 62335 62336

</pre>

 

=={{header|Julia}}==

 

function nsmooth(N, needed)

 

testnsmoothfilters()

<pre>

The first 25 n-smooth numbers for n = 2 are: [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216]

=={{header|Kotlin}}==

{{trans|Go}}

 

var primes = mutableListOf<BigInteger>()

println()

}

{{out}}

<pre>The first 25 2-smooth numbers are:

The 30,000th to 30,019 521-smooth numbers are:

[62287, 62288, 62291, 62292, 62300, 62304, 62307, 62308, 62310, 62315, 62320, 62321, 62322, 62325, 62328, 62329, 62330, 62331, 62335, 62336]</pre>

 

=={{header|Pascal}}==

 

 

type

 

 

var

HNum:tHamNum;

 

var

Begin

end;

 

var

begin

 

end;

 

var

begin

end;

 

var

Begin

 

 

 

 

 

=={{header|Perl}}==

{{libheader|ntheory}}

use warnings;

use feature 'say';

} until @Sm == $cnt;

say join ' ', @Sm;

 

{{out}}

{{libheader|Phix/mpfr}}

{{trans|Julia}}

{{out}}

<pre>

=={{header|Python}}==

{{trans|C#}}

 

def isPrime(n):

print

 

{{out}}

<pre>The first 2 -smooth numbers are:

The 30000 to 3019 521 -smooth numbers are:

[62287, 62288, 62291, 62292, 62300, 62304, 62307, 62308, 62310, 62315, 62320, 62321, 62322, 62325, 62328, 62329, 62330, 62331, 62335, 62336]</pre>

 

=={{header|Raku}}==

{{works with|Rakudo|2019.07.1}}

 

cache my \Smooth := gather {

my %i = (flat @list) Z=> (Smooth.iterator for ^@list);

put "\n{$start}th through {$start+19}th {@primes[$i]}-smooth numbers:\n" ~

smooth-numbers(|@primes[0..$i])[$start - 1 .. $start + 18];

 

{{out}}

 

=={{header|REXX}}==

numeric digits 200 /*be able to handle some big numbers. */

parse arg LOx HIx LOn HIn . /*obtain optional arguments from the CL*/

end /*j*/; return

/*──────────────────────────────────────────────────────────────────────────────────────*/

{{out|output|text=&nbsp; when using the default inputs:}}

<pre>

=={{header|Ruby}}==

{{trans|Python}}

return n | 1 == 3 if n < 5 # n: 2,3|true; 0,1,4|false

sqrtN = Integer.sqrt(n)

pc = -1 # initial P3 prime candidates value

print nsmooth(prime, 30019)[29999..-1] # for ruby >= 2.6: (..)[29999..]

puts

 

{{out}}

=={{header|Rust}}==

{{trans|C}}

if n < 2 {

return false;

}

 

let primes = find_primes(2, n);

let num_primes = primes.len();

for i in 0..num_primes {

index.push(0);

}

for i in 1..count {

for p in 0..num_primes {

if queue[p] == result[i - 1] {

index[p] += 1;

}

}

}

}

}

result

}

}

 

{{out}}

 

=={{header|Sidef}}==

var s = primes.len.of { [1] }

{

var g = smooth_generator(p.primes)

say ("3,000th through 3,002nd #{'%2d'%p}-smooth numbers: ", 3002.of { g.run }.last(3).join(' '))

{{out}}

<pre>

 

Optionally, an efficient algorithm for checking if a given arbitrary large number is smooth over a given product of primes:

 

return true if (n == 1)

var a = {|n| is_smooth_over_prod(n, k) }.first(30_019).last(20)

say ("30,000th through 30,019th #{p}-smooth numbers: ", a.join(' '))

{{out}}

<pre>

{{libheader|AttaSwift BigInt}}

 

import Foundation

 

for n in 503...521 where n.isPrime {

print("The 30,000...30,019 \(n)-smooth numbers are: \(smoothN(n: BigInt(n), count: 30_019).dropFirst(29999).prefix(20))")

 

{{out}}

{{libheader|Wren-math}}

{{libheader|Wren-big}}

 

// cache all primes up to 521

System.print(nSmooth.call(i, 30019)[29999..-1])

System.print()

 

{{out}}

{{trans|Go}}

{{libheader|GMP}} GNU Multiple Precision Arithmetic Library and primes

 

fcn nSmooth(n,sz){ // --> List of big ints

}

ns

p:=BI(1); while(p<29) { smallPrimes.append(p.nextPrime().toInt()) }

 

println("\nThe 30,000th to 30,019th %d-smooth numbers are:".fmt(p));

println(nSmooth(p,30019)[29999,*].concat(" "));

{{out}}

<pre style="height:45ex">