Project Euler 10

Project Euler - Problema 10
Calcular a soma dos números primos abaixo de 2000000.

Function testPrimo([Long]$n) {
    if (($n % 2) -eq 0) { return $false }
    [Long]$c = 3
    while (($c * $c) -le $n) {
        if (($n % $c) -eq 0) { return $false } 
        else { $c +=2 }
    }
    return $true;
}

Function _Main([Int32]$max) {
    [Long] $somaPrimos = 0
    [Long] $num = 3
 
    while ($num -lt $max) {
        if ((testPrimo $num) -eq $true) {
            $somaPrimos += $num;
        }
        $num += 2; #com exceção do 2, todo primo é ímpar
    }
    $somaPrimos += 2
    Write-Host "A soma dos primos abaixo de $max é: $somaPrimos"
}

Clear-Host
_Main 2000000

A soma dos primos abaixo de 2000000 é: 142913828922

Project Euler - 7

Nesse problema proposto em Project Euler, deseja-se descobrir qual é o 10001° número primo.

Uma possibilidade de implementação seria:

Function testPrimo([Int32]$n) {
    if (($n % 2) -eq 0) { return $false }
    [Int32]$c = 3
    while (($c * $c) -le $n) {
        if (($n % $c) -eq 0) { return $false } 
        else { $c +=2 }
    }
    return $true;
}

Function _Main([Int32]$indPrimo) {
    [Int32] $qtdePrimos = 1
    [Int32] $enesimoPrimo = 1
 
    while ($qtdePrimos -lt $indPrimo) {
        $enesimoPrimo += 2;
        if (testPrimo($enesimoPrimo)) {
            $qtdePrimos++;
        }
    }
    Write-Host "O $indPrimo° número primo é: $enesimoPrimo"
}

Clear-Host
_Main 10001

O 10001° número primo é: 104743

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