4
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Alright, are there resources you can point me to that could help me improve my algorithm? I already have cut all even numbers from both test pools, and also cut the number of division checks by half. Is this going to require a complete overhaul, or am I just simply missing a few more parts? \$\endgroup\$ – NebulaCoding Nov 9 '18 at 13:27
  • 2
    \$\begingroup\$ Sorry, I'm too busy with other things ATM to get in deeper. I saw a japanese link translated via google that used the sieve of erasthotenes with a bit array - but the code got mangled by the translation. I think that code was along the lines of this c#-answer on SO. Embedding c# code in PowerShell is not an option? \$\endgroup\$ – LotPings Nov 9 '18 at 14:03
  • \$\begingroup\$ It might be, I just don't have experience with C#. I'll look into implementing the sieve in PS, I've seen it brought up a few times. \$\endgroup\$ – NebulaCoding Nov 9 '18 at 14:15
  • 1
    \$\begingroup\$ After 2 and 3, all other prime numbers are of the form 6n ± 1, which will speed up your search. For the fastest time you probably need the Sieve of Eratosthenes. According to the Prime Number Theorem, your sieve will need to extend up to about 110,000. \$\endgroup\$ – rossum Nov 21 '18 at 19:16
-2
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ An alternate solution is not considered a good answer on code review, a good answer may not contain any code at all. The point of a code review is to help the OP improve their code. An alternate solution doesn't discussed the OP's code at all. \$\endgroup\$ – pacmaninbw Apr 22 at 21:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.