All pastes #507826 Raw Edit

Something

public text v1 · immutable
·published 2007-05-24 19:21 UTC
rendered paste body
my $n=1000000;

# sieve and compute number of distinct factors

my @p; # $p[$k] will be smallest prime factor of $k
my @c; # number of distinct prime factors

for ($i=2;$i<$n;$i++) {
    if (!$p[$i]) {
	$p[$i] = $i;
	for ($j=$i;$j<$n/$i;$j++) {
	    $p[$i*$j] = $i if (!$p[$i*$j]);
	}
    }

    my $f = 0;
    for ($j=$i;$j>1;$j=$j/$f) {
	if ($f != $p[$j]) {
	    $c[$i]++;
	    $f = $p[$j];
	}
    }

    if (($c[$i]==4)&&($c[$i-1]==4)&&($c[$i-2]==4)&&($c[$i-3]==4)) {
	my $k;
	for ($k=$i-3;$k<=$i;$k++) {
	    print "$k:";
	    for ($j=$k;$j>1;$j=$j/$p[$j]) {
		print " $p[$j]";
	    }
	    print "\n";
	}
    }
}