Radical of an integer: Difference between revisions

</pre>

=={{header|Nim}}==

<syntaxhighlight lang="Nim">import std/[math, strformat, strutils]

const N = 1_000_000

### Build list of primes.

func isPrime(n: Natural): bool =

## Return true if "n" is prime.

## "n" should not be a mutiple of 2 or 3.

var k = 5

var delta = 2

while k * k <= n:

if n mod k == 0: return false

inc k, delta

delta = 6 - delta

result = true

var primes = @[2, 3]

var n = 5

var step = 2

while n <= N:

if n.isPrime:

primes.add n

inc n, step

step = 6 - step

### Build list of distinct prime factors to

### compute radical and distinct factor count.

var primeFactors: array[1..N, seq[int]]

for p in primes:

for n in countup(p, N, p):

primeFactors[n].add p

template radical(n: int): int = prod(primeFactors[n])

template factorCount(n: int): int = primeFactors[n].len

### Task ###

echo "Radical of first 50 positive integers:"

for n in 1..50:

stdout.write &"{radical(n):2}"

stdout.write if n mod 10 == 0: '\n' else: ' '

echo()

for n in [99_999, 499_999, 999_999]:

echo &"Radical for {insertSep($n):>7}: {insertSep($radical(n)):>7}"

echo()

echo "Distribution of the first one million positive"

echo "integers by numbers of distinct prime factors:"

var counts: array[0..7, int]

for n in 1..1_000_000:

inc counts[factorCount(n)]

for n, count in counts:

echo &"{n}: {insertSep($count):>7}"

echo()

### Bonus ###

echo "Number of primes and powers of primes"

echo "less than or equal to one million:"

var count = 0

const LogN = ln(N.toFloat)

for p in primes:

inc count, int(LogN / ln(p.toFloat))

echo insertSep($count)

</syntaxhighlight>

{{out}}

<pre>Radical of first 50 positive integers:

1 2 3 2 5 6 7 2 3 10

11 6 13 14 15 2 17 6 19 10

21 22 23 6 5 26 3 14 29 30

31 2 33 34 35 6 37 38 39 10

41 42 43 22 15 46 47 6 7 10

Radical for 99_999: 33_333

Radical for 499_999: 3_937

Radical for 999_999: 111_111

Distribution of the first one million positive

integers by numbers of distinct prime factors:

0: 1

1: 78_734

2: 288_726

3: 379_720

4: 208_034

5: 42_492

6: 2_285

7: 8

Number of primes and powers of primes

less than or equal to one million:

78_734