Prime numbers c#

Question

很抱歉，但我必须问一个非常简单的问题。我的问题是，我想生成质数直到一个最大值。

下面是我的代码:

    for (int i = 2; i <= max - 1; i++)
        {
            System.Threading.Thread.Sleep(1000);
            if (Progress != null)
            {
                if (max%i == 0)
                    Console.WriteLine(i);
            }
        }  

我的代码不工作，我不知道为什么…

你能帮帮我吗?

Answer 1

提示1:算法优化

你不需要一直到最大值。你只需要求它的平方根。

与我一起思考这个例子:如果100除以50，它首先被捕获为除以2。所以你只需要从10开始，在那之后找到的任何除数，它的对应数在之前就已经找到了。

但这只是你如何最优地发现一个特定的数字是否是素数。

提示2:IsNumberPrime() Method

首先，你必须有一个方法来确定一个特定的数是否是素数。记住这里的提示1。

提示3:这次做对了

在您遵循提示1和2之后，现在您可以循环并确定比最大值更低的最大素数。

结论

抱歉，这里没有代码，只有一般方向。帮你做作业对你没有帮助。

Answer 2

虽然您可以检查每个数字的素数，但这是浪费工作。有很多数字你甚至不需要考虑。除了2以外的偶数。还有更多的技巧，比如关于6的倍数(谷歌一下)

如果要生成素数，请使用生成素数的算法。看起来很明显，对吧?但测试素数的算法不属于这一类。埃拉托色尼的筛子很好，阿特金的筛子更好。

如果你无论如何都要检查数字的素数(但说真的，不要这样做)，试除法是最糟糕的相同算法，除非你的数字总是很小(比如小于10k)。使用Miller Rabin测试的确定性版本，有已知的上界(不是完整的，因为你有已知的上界，否则你会生成所有的PositiveInfinity素数)。

Answer 3

我就傻傻地给你一些我前一段时间在信息学课上写的代码。所有东西都是长，因为它最初被设计为质数，检查一些太大的数字。

ulong min = 0;
ulong max = 100000;
ulong i = 0;
ulong sqrt = 0;
ulong j = 0;
bool prime = true;
for (i = min; i <= max; i += 2)
{
  prime = true;
  sqrt = Math.Sqrt(i) + 1;
  if (i % 2 == 0) prime = false;
  else for (j = 3; j < sqrt; j += 2)
  {
    if (i % j == 0)
    {
      prime = false;
      break;
    }
  }
  if(prime)
  {
    Console.WriteLine(i);
  }
}

这是稍微编辑过的，所以我不完全确定这是否会像预期的那样工作，但它不能太难编辑自己。

Answer 4

检验一个数是否为素数的方法:

bool IsPrime(int number)
{
    for (int i = 2; i < sqrt(number); i++)
    {
         if (number%i == 0) return false;
    }
    return true;
}

对所有整数调用此方法，直到max:

for (int crt = 1; crt <= max; crt++)
{
    if (IsPrime(crt))
    {
         Console.WriteLine(crt);
    }
}