Project Euler - 3

O problema 3 do Project Euler é sobre decompor um número em seus fatores primos.

Vamos demonstrar 2 soluções (o maior fator é 6857) com seus respectivos tempos de cálculo.

Function LargestPrimeFactor([Long]$Num) {
    Write-Host "Força Bruta"
    [Long]$sqrtNum = [math]::Sqrt($Num) 
    $maxFactor = 2
    $prime = 2
    Write-Host "Fatores Primos de $Num : " -NoNewline
    While ($Num -gt 1) {
        If (($Num % $prime) -eq 0) {
            $maxFactor = $prime
            $Num = $Num / $prime
            Write-Host "$prime," -NoNewline
        }
        Else {
            If ($prime -lt $sqrtNum) { $prime = getNextPrime($prime+1) }
        }
    }
    Return $maxFactor
}

Function getNextPrime([Long]$p) {
    [Int32]$sum = 0
    While ($sum -eq 0) {
        For([Long]$j=1; $j -le $p; $j++) {
            If($p % $j -eq 0) { $sum++ }
        }

        If ($sum -eq 2) { Return $p }
        Else { 
            $sum = 0 
            $p++
        }
    }
}

Function FastLargestPrimeFactor([Long]$Num) {
    Write-Host "Método Rápido"
    Write-Host "Fatores Primos de $Num : " -NoNewline
    [Long]$i = 2
    While (($i * $i) -lt $Num) {
        While (($Num % $i) -eq 0) { 
            Write-Host "$i," -NoNewline
            $Num = $Num / $i 
        }
        $i = $i + 1
    }
    Write-Host $Num -NoNewline
    Return $Num
}
Clear-Host
$time = New-Object System.Diagnostics.Stopwatch
$time.Start()
$maxFactor = LargestPrimeFactor 600851475143
$time.Stop()
$ts = $time.Elapsed
Write-Host ""
Write-Host "O maior fator primo de 600851475143: $maxFactor"
Write-Host "Tempo de Cálculo - Força Bruta:"
Write-Host $ts.Seconds "segundos e" $ts.Milliseconds "milissegundos"
Write-Host "----------------------------------------------------"
$time2 = New-Object System.Diagnostics.Stopwatch
$time2.Start()
$maxFactor2 = FastLargestPrimeFactor 600851475143
$time2.Stop()
$ts2 = $time2.Elapsed
Write-Host ""
Write-Host "O maior fator primo de 600851475143: $maxFactor2"
Write-Host "Tempo de Cálculo - Método Rápido:"
Write-Host $ts2.Seconds "segundos e" $ts2.Milliseconds "milissegundos"

Força Bruta
Fatores Primos de 600851475143 : 71,839,1471,6857,
O maior fator primo de 600851475143: 6857
Tempo de Cálculo - Força Bruta:
7 segundos e 79 milissegundos
----------------------------------------------------
Método Rápido
Fatores Primos de 600851475143 : 71,839,1471,6857
O maior fator primo de 600851475143: 6857
Tempo de Cálculo - Método Rápido:
0 segundos e 29 milissegundos