0

这个特定的问题不涉及循环，我看到的大多数答案都涉及循环。这是我正在阅读的一本书的挑战。不，我不是学生（38 岁）我实际上正在转换职业，所以我决定开始学习如何编程。我正在阅读的书名为“C#/Joes 2 Pros 简介”。

这是我到目前为止的代码。我知道很可能有更好的方法来使用我可能没有很好掌握的东西来做到这一点。例如，我知道什么是“布尔”，但还没有在我的任何编码中使用它。因此，很难实施。

    int myChoice;
    Console.Write("Please enter a number: ");
    myChoice = int.Parse(Console.ReadLine());

    if (myChoice >= 1 && myChoice % myChoice == 0)
    {
        Console.WriteLine("That's correct, {0} is a prime number.", myChoice);
    }
    else
    {
        Console.WriteLine("That is not a prime number.");
    }

    Console.ReadLine();

好的，如您所见，程序要求用户输入一个数字。由 if 语句确定，如果该数大于或等于 1 并且该数可被自身整除且没有余数，则该语句为真。

我知道有一种更好的方法可以找出输入的数字是否是素数，但我就是不知道它是什么。该程序执行我期望它执行的操作，除了确定数字是否为素数。

这里只是一点背景。你在屏幕上看到的只是我对 C# 的了解程度。除了你看到的，我可能迷路了。

有什么建议么？

4

2 回答 2

1

如果您的数字n很小，则可以简单地测试所有小于sqrt(n)除数的数字；如果它们都不除n，则n是素数：

function isPrime(n)
    d := 2
    while d * d <= n
        if n % d == 0
            return Composite
        d := d + 1
    return Prime

对于较大的数字，一种合理的素性检验是米勒-拉宾检验；它可以被愚弄（错误地宣称一个合数是素数），但可能性很小。从一个强伪素测试开始：

function isStrongPseudoprime(n, a)
    d := n - 1; s := 0
    while d is even
        d := d / 2; s := s + 1
    t := powerMod(a, d, n)
    if t == 1 return ProbablyPrime
    while s > 0
        if t == n - 1
            return ProbablyPrime
        t := (t * t) % n
        s := s - 1
    return DefinitelyComposite

函数返回的每个a可能是n的素数的见证；对它们进行足够多的测试，你就会对n实际上是素数有了信心：

function isPrime(n)
    for i from 1 to k
        a := randint(2 .. n-1)
        if isStrongPseudoprime(n, a) == DefinitelyComposite
            return DefinitelyComposite
    return ProbablyPrime

变量k是您要执行的试验次数；10 到 25 之间的某个值通常是一个合理的值。该powerMod(b,e,m)函数返回b ^ e (mod m )。如果您的语言不提供该功能，您可以像这样有效地计算它：

function powerMod(b, e, m)
    x := 1
    while e > 0
        if e % 2 == 1
            x := (b * x) % m
        b := (b * b) % m
        e := floor(e / 2)
    return x

如果你对这个测试背后的数学感兴趣，我谦虚地推荐我博客上的用质数编程的文章。

于 2013-06-05T13:01:58.367 回答
1

测试素数还有另一个非常具有挑战性的要求，它不能除以任何其他数字。例如 4 大于零并且 4 % 4 = 0。但 4 不是素数，它等于 2x2。

测试素数相当困难。大多数入门编程书籍都希望您尝试使用埃拉托色尼筛法，这是一种确定数字是否为素数的古老方法。wiki 页面为此提出了一种算法。基本上，您在数组中生成从 1 到 100 的数字，并删除那些不是素数的数字，留下从 1 到 100 的所有素数。

于 2013-06-05T02:09:37.950 回答