#!/usr/bin/perl
use strict;
use warnings;

use Data::Dumper;

my @nlist = qw( 3 24 8 17 23 14 17 9 16 24 25 11 22 14 14 8 19 16 15 8
+ );
my @key_list = ( 'A' .. 'Z' );

my %hoa;

foreach my $num ( @nlist ) {
    my $key;

    foreach my $check_key ( @key_list ) {
        if(
            not exists $hoa{ $check_key }
            or $num % $hoa{ $check_key }[ 0 ] == 0
        ) {
            $key = $check_key;
            last;
        }
    }

    die "Key list depleted" if not defined $key;

    push @{ $hoa{ $key } }, $num;
}

print Dumper \%hoa;
[download]

My problem with the algorithm you outlined, though, is that if the list contains a 9 earlier than a 3, then 9 will be considered a denominator different from 3. Is that what you intend?

If not, then the solution is to test the candidate denominator and the number against each other both ways, and to make sure to keep the smallest number under each key at the front of the list. (Except remembering to make 1 a special case, that is.) In that case you will get your input list segmented by the smallest prime factor products present in the list.

Makeshifts last the longest.

my @nlist = (3,24,8,17,23,14,17,9,16,24,25,11,22,14,14,8,19,16,15,8);
my @key_list = ('A'..'Z');

my @lookup;
my %hash;

NLIST:
foreach my $num (@nlist) {
   foreach (@lookup) {
      my ($factor, $key) = @$_;
      if ($num % $factor == 0) {
         push(@{$hash{$key}}, $num);
         next NLIST;
      }
   }

   my $key = shift(@key_list);
   push(@lookup, [$num, $key]);
   $hash{$key} = [ $num ];
}

require Data::Dumper;
print(Data::Dumper::Dumper(\%hash));
[download]

output: (reformatted for readability)

$VAR1 = {
          'A' => [3,24,9,24,15],
          'B' => [8,16,8,16,8],
          'C' => [17,17],
          'D' => [23],
          'E' => [14,14,14],
          'F' => [25],
          'G' => [11,22],
          'H' => [19]
        };
[download]

Just a note about my code design:

I didn't need to use a seperate lookup structure. I could just have interated over the keys of %hash (like Aristotle did). However, iterating over an array will return consistent results whereas iterating over a hash will not.

Given
@nlist = (9,3,27);
always gives
'A' => [9,27], 'B' => [3]
with my code, but can give either
'A' => [9,27], 'B' => [3]
or
'A' => [9], 'B' => [3,27]
(unpredicatbly) when iterating through %hash.

Did you read my code? I don’t iterate over any hash anywhere. Your claim that my code may produce inconsistent results is false.

You stuck to the OP’s approach of shifting from the @key_list, which makes it unduly complicated to achieve consistency. I did not, so my code is simpler, but it is just as consistent.

Makeshifts last the longest.

First of all, the answer you got manually was wrong. 'F' contains 25, not 16, all the 16's went to 'B' already.

use strict;
use Data::Dumper;


my @nlist = (3,24,8,17,23,14,17,9,16,24,25,11,22,14,14,8,19,16,15,8);

my @key_list = ('A'..'Z');

my $hoa;

my $key_index = -1;
while (@nlist) {
    $hoa->{$key_list[++$key_index]}[0] = splice(@nlist, 0, 1);
    my $i = 0;
    while ($i <= $#nlist) {
        if ($nlist[$i] % $hoa->{$key_list[$key_index]}[0]) {
            $i ++;
        } else {
            push @{$hoa->{$key_list[$key_index]}}, splice(@nlist, $i, 
+1);
        }
    }    
}

print Dumper $hoa ;
[download]

my @nlist = (3,24,8,17,23,14,17,9,16,24,25,11,22,14,14,8,19,16,15,8);

my @key_list = ('A'..'D');

my ($result, @ans, $i) ;

for my $num ( @nlist ) {
    $i = 0;
    while ( 1 ) {
        if ( ! defined @{$ans[$i]}  or  0 == $num % ${$ans[$i]}[0] ){
            push @{$ans[$i]}, $num;
            last;
        }
        ++$i;
    }
}

$result->{ shift @key_list } = $_ for  @ans ;
[download]