c# - 素数代码

Question

为什么这段代码不起作用？它应该使我所有的素数都达到 10，但我只得到数字 2 和 3。

bool m = true;
int i;
int a;
for (a = 2; a <= 10; a++)
{
    for (i = 2; i < a; i++) 
    {
        if (a % i == 0)
        {
            m = false;
        }
    }

    if (m == true)
    {
        Console.WriteLine(a);
    }
}
Console.ReadKey();

Answer 1

两个主要问题。

1. 你永远不会重置m，所以一旦你找到一个非素数，你就会在剩下的迭代中被这个结果卡住。
2. 当您测试一个非素数时，您只需继续进行一次，您会发现一个并覆盖您的结果。由于你写它的方式，它不会有那么大的问题i-1 % i，== 0但如果你早点爆发，你可以为自己节省很多时间。（您还可以通过测试来节省大量时间，Math.Sqrt(a)因为在那之后每个符合条件的除数都已经过测试（a / i = b与此相同，a / b = i因此您只需要检查其中一个））

Answer 2

for (a = 2; a <= 10; a++)
{
    for (i = 2; i < a; i++)
    {
        if (a % i == 0)
        {
            m = false;
        }
    }

    if (m == true)
    {
        Console.WriteLine(a);
    }

    m = true; //<<******* Add this line
}

当然，一些加速总是可能的

for (a = 2; a <= 100; a++)
{
    for (i = 2; i < Math.Sqrt(a); i++) //<--- http://en.wikipedia.org/wiki/Prime_number#Trial_division
    {
        if (a % i == 0)
        {
            m = false;
            break; //<---- a is not prime, quit the inner loop immediately.
        }
    }

    if (m == true)
    {
        Console.WriteLine(a);
    }

    m = true; //<<******* Add this line
}

Answer 3

m通过非素数后，您不会重置。

Answer 4

你真的需要一个布尔变量吗？如果您需要做的只是打印值，那么您可以跳过布尔值：

int i;
int a;
for(a=2; a<=10; a++) {
    for(i=2; i<a; i++) {
        if(a % i == 0) {
            Console.WriteLine(a);
            break;
        }
    }
}

请注意，break强制退出内部for，因此您可以继续外部的下一次迭代for。

---

更正：上面的代码打印非质数。所以是的，您可能需要布尔变量来跟踪素数。但是如果你想让它正常工作，你必须打破内部：

int i;
int a;
bool m;
for(a=2; a<=10; a++) {
    m = true
    for(i=2; i<a; i++) {
        if(a % i == 0) {
            m = false;
            break;
        }
    }
    if (m) {
        Console.WriteLine(a);
    }
}

当然，不用布尔变量也可以得到相同的结果，只需在 break 之后再进行一次比较即可：

int i;
int a;
for(a=2; a<=10; a++) {
    for(i=2; i<a; i++) {
        if(a % i == 0) {
            break;
        }
    }
    if(a % i != 0) {
        Console.WriteLine(a);
    }
}