Project Euler - 5

Uma solução para o problema 5 do Project Euler.

[Int32]$Num = 20;
 
while ((($Num % 2) -ne 0) -or (($Num % 3) -ne 0) -or (($Num % 4) -ne 0) `
      -or (($Num % 5) -ne 0) -or (($Num % 6) -ne 0) -or (($Num % 7) -ne 0) `
      -or (($Num % 8) -ne 0) -or (($Num % 9) -ne 0) -or (($Num % 10) -ne 0) `
      -or (($Num % 11) -ne 0) -or (($Num % 12) -ne 0) -or (($Num % 13) -ne 0) `
      -or (($Num % 14) -ne 0) -or (($Num % 15) -ne 0) -or (($Num % 16) -ne 0) `
      -or (($Num % 17) -ne 0) -or (($Num % 18) -ne 0) -or (($Num % 19) -ne 0) `
      -or (($Num % 20) -ne 0)) {

      $Num+=20;
}

Clear-Host
Write-Host "O menor número divisível por todos os números de 1 a 20, sem resto, é: $Num"

O menor número divisível por todos os números de 1 a 20, sem resto, é: 232792560

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