読者です 読者をやめる 読者になる 読者になる

Problem 3

euler perl

素因数の最大値を求める問題。問題の数値が大きいからそれなりに時間がかかりますね。
なんでかは知らないけど、素因数は目的の数の二乗根より小さいのでそれで計算時間を短縮。

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

print "max prime factor is ", p3(600851475143), "\n"; # 6857

sub p3
{
  my ($num) = @_;

  my $max_prime_factor = 1;
  my $limit = sqrt($num);

  while(1){
    if($num % 2 == 0){
      $max_prime_factor = 2;
      $num /= 2;
    }
    else{
      last;
    }
  }

  for(my $i = 3; $i <= $limit;){
    if($num % $i == 0){
      $max_prime_factor = $i;
      $num /= $i;
    }
    else{
      $i += 2;
    }
  }

  $max_prime_factor = $num if $max_prime_factor == 1;

  return $max_prime_factor;
}