Euler Problem 7 (finding the 10001st prime) in Powershell

Question

I am having issue making this code more efficient. The problem to be solved is as follows:

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10,001st prime number?

I'm looking to complete this in powershell. My code runs well up until about 4.8k primes.

$incNum1 = 1
$incNum2 = 2
$divisNum = 2 * $incNum2 - 1
$highestNum = 0
$k = 1
$nextNum = 2 * $incNum1 + 1

while($k -lt 6000){

    $upTo = [int][Math]::Ceiling(($nextNum / 2))

    $break = $false

    while($divisNum -lt $upTo){
        $modRes = $nextNum % $divisNum


        if($modRes -eq 0){

            $break = $true

            break
        }

        $incNum2++
        $divisNum = 2 * $incNum2 - 1
    }

    if(!$break){

        $highestNum = $nextNum

        echo $nextNum

        $k++
    }

    $incNum2 = 2
    $divisNum = 2 * $incNum2 - 1

    $incNum1++

    $nextNum = 2 * $incNum1 + 1
}

echo $highestNum

Answer 1

I'd start with

• removing redundancy
• measuring the time automatically
• output to screen slows down, comment it out

depending on the speed of the computer used I get results of ~74..120 seconds.
Compared with 0.450 secs here with matlalb there IS potential to get better ;-)

## Q:\Test\2018\11\08\CR_207250.ps1

$StartTime = get-date
$PrimeNo = 10001

$incNum1 = 0
$highestNum = 0
$k = 1

while($k -lt $PrimeNo){
    $incNum2 = 2
    $divisNum = 2 * $incNum2 - 1
    $incNum1++
    $nextNum = 2 * $incNum1 + 1

    $upTo = [Math]::Ceiling(($nextNum / 2))
    $break = $false
    while($divisNum -lt $upTo){
        $modRes = $nextNum % $divisNum

        if($modRes -eq 0){
            $break = $true
            break
        }
        $incNum2++
        $divisNum = 2 * $incNum2 - 1
    }
    if(!$break){
        $highestNum = $nextNum
#        "{0}:{1}" -f $k,$nextNum
        $k++
    }
}

"## PrimeNo: {0} is {1} calculated in {2} seconds" -f $PrimeNo,$highestNum,
    ((Get-Date)-$StartTime).TotalSeconds

## PrimeNo: 10001 is 104743 calculated in 73,6911884 seconds
## PrimeNo: 10001 is 104743 calculated in 118,3481173 seconds

Answer 2

You could calculate the upper bound based on Prime Number Theory. Once you have this number you can implement the Sieve of Eratosthenes. One possible implementation is using a HashTable with every number from 2 to your upperbound as the key and a bool indicating prime status for the value. Iterate through the sieve marking each number. As you find a new prime increment a counter and when the counter matches n return that prime.