Project Euler meets Powershell - Problem #3

amonkeyseulersolutions:

I’ve read that an integer p > 1 is prime if and only if the factorial (p - 1)! + 1 is divisible by p. So I’ve written this: Read More

Here’s the fixed version…

function isprime {
[cmdletbinding()]
param($x)
	if ($x -lt 1) {
		return "Has to be on a positive integer"
	}

	# An integer p > 1 is prime if and only if the factorial (p - 1)! + 1 is divisible by p
	
	$factorial = factorial ($x-1)
	Write-Verbose "Factorial: $($factorial.ToString())"
	[System.Numerics.BigInteger] $remainder = ($factorial + 1) % $x
	Write-Verbose "Remainder: $($remainder.ToString())"
	
	if ($remainder -eq 0) {
		return $true
	} else {
		return $false
	}
}

And using that the largest prime factor can be found with this:

function Get-LargestPrimeFactor {
[cmdletbinding()]
param([int] $x)
	if ($x -lt 1) {
		return "Has to be on a positive integer"
	}
	$i = [int] [System.Math]::Sqrt($x)
	Write-Verbose "Square root: $i"
	for ( $i ; $i -gt 1 ; $i -= 1 ) {
		Write-Verbose "checking: $i"
		if ( ($x % $i) -eq 0 ) {
			Write-Verbose "Factor: $i"
			if (isprime $i) {
				Write-Verbose "Prime Number: $i"
				break
			}
		}	
	}
	if ($i -gt 1) {
		Write-Output "The largest prime is $i"
	} else {
		Write-Output "No prime factor"
	}
}


And just for completeness a function that returns them all:
function Get-PrimeFactors {
[cmdletbinding()]
param($x)
	if ($x -lt 1) {
		return "Has to be on a positive integer"
	}
	$output = @()
	$i = [int] [System.Math]::Sqrt($x)
	Write-Verbose "Square root: $i"
	for ( $i ; $i -gt 1 ; $i -= 1 ) {
		Write-Verbose "checking: $i"
		if ( ($x % $i) -eq 0 ) {
			Write-Verbose "Factor: $i"
			if (isprime $i) {
				Write-Verbose "Prime Number: $i"
				$output = $output + $i
			}
		}	
	}
	$output
}

which works for low number but gets the following error for the for the number from project euler…

PS C:\Users\Matt> Get-LargestPrimeFactor 600851475143
The script failed due to call depth overflow.  The call depth reached 1001 and the maximum is 1000.
    + CategoryInfo          : InvalidOperation: (1001:Int32) [], ParentContainsErrorRecordException
    + FullyQualifiedErrorId : CallDepthOverflow

it needs a couple of for loops? where depends on what is being called more than 1000 times?