使用 powershell 检查数字是否为质数

Question

这是我检查随机数是否为素数的脚本：

[int]$nombre = Get-Random -Minimum 1 -Maximum 10
$nombre
$j=0

if($nombre -lt 2) { " $nombre n'est pas premier " }

else {

for($i=1; $i -le $nombre; $i++){

if( $nombre%$i -eq 0) {$j++}

 }
 if($j -eq 2 ) { "Le nombre est  premier "}
 else {"Ce nombre est premier"}
   } 

当我执行脚本时，我得到错误的结果，例如 4 是素数。有解决办法吗？ 谢谢你

Answer 1

我只是想改进现有的答案。

对我来说，这很明显，我不明白为什么没有人指出，如果数字是平方数，它可以通过跳过 for 循环来简化整个过程，只需在代码之前添加

if ([math]::Sqrt{$number} -is [int]) {$prime = $false}

循环，根据定义平方数是合数，为什么没人注意到呢？

更新：基于之前答案的更好的函数，它将 $false 分配给负数、零、分数和非数字：

function Test-Prime {
    param(
    [Parameter(ValueFromPipeline=$true)]
    $number
    )
    
   Process {
    $prime = $true;
    if ($number -isnot [int]) {$prime = $false}
    elseif ($number -le 0) {$prime = $false}
    else {
        if ($number -eq 1) {
            $prime = $false;
        }
        if ($number -gt 3) {
            $sqrt = [math]::Sqrt($number); 
            if ($sqrt -is [int]) {$prime = $false}
            else {
                for($i = 2; $i -le $sqrt; $i++) {
                    if ($number % $i -eq 0) {
                        $prime = $false;
                        break;
                    }
                }
            }
        }
    }
    return $prime;
}

}

Answer 2

你需要从 3 开始你的 for 循环，而不是 1。一切都可以被 1 整除，你已经测试过被 2 整除。

您的代码有很多问题。 j 计数器就是其中之一。包括 $nombre 的循环也是其中之一。

function Test-Prime {
    param(
        [Parameter(ValueFromPipeline=$true)]
        [int]$number
        )

    Process {
        $prime = $true;

        if ($number -eq 1) {
            $prime = $false;
        }
        if ($number -gt 3) {
            # limit loop to max sqrt($number)
            $sqrt = [math]::Sqrt($number); 
            for($i = 2; $i -le $sqrt; $i++) {
                if ($number % $i -eq 0) {
                    # we found it is not prime
                    $prime = $false;
                    break;
                }
            }
        }

        return $prime;
    }
}

# test for all values between 1 and 100
1..10 | %{ Write-Host " $_ $( Test-Prime $_)" }

哪个打印

1 错误
2 正确
3 正确
4 错误
5 正确
6 错误
7 正确
8 错误
9 错误
10 错误

Answer 3

这是给您的另一个代码片段。它会向您显示 1000 以内的第一个素数。

cls
$primelist = [System.Collections.ArrayList]::new()
foreach($number in 0..1000) {
    if ($number -le 3) {
        $isprime = $number -gt 1
        $maxDiv  = 2
    } else {
        $isprime = $true
        foreach($div in $primeList) {
            if ($number % $div -eq 0) {
                $isprime = $false
                if ($maxDiv*$maxDiv -lt $number){$maxDiv++}
                break
            }
            if ($div -ge $maxDiv) {break}
        }
    }
    if ($isprime) {[void]$primelist.Add($number)}
}
write-host ([string]::Join(',',$primeList.ToArray()))

对于较大的素数，我建议使用 Rabin-Miller 函数。详情请看这里：如何通过密码学提供者生成大素数？

Answer 4

1..2000|?{('1'*$_) -notmatch '^1?$|^(11+?)\1+$'}