#!/usr/bin/perl

# Perl program for A022559 by Daniel Suteu (21 December 2018).

use strict;
use warnings;

use ntheory qw(vecsum logint sqrtint rootint prime_count forprimes);

sub prime_power_count {
    my ($n) = @_;
    vecsum(map { prime_count(rootint($n, $_)) } 1 .. logint($n, 2));
}

sub a {
    my ($n) = @_;

    return 0 if ($n <= 1);

    my $s = sqrtint($n);
    my $u = int($n/($s + 1));

    my $total = 0;
    my $prev = prime_power_count($n);

    for my $k (1 .. $s) {
        my $curr = prime_power_count(int($n/($k+1)));
        $total += $k * ($prev - $curr);
        $prev = $curr;
    }

    forprimes {
        foreach my $k (1 .. logint($u, $_)) {
            $total += int($n / $_**$k);
        }
    } $u;

    return $total;
}

printf("%s\n", join(', ', map { a($_) } 0..100));