4

我正在尝试根据用户输入生成素数。这是我到目前为止所拥有的，但我似乎无法弄清楚：

Console.Write("Please enter the number of prime numbers you would like to see:");
int numberOfPrimes = Convert.ToInt32(Console.ReadLine());

for (int x = 0; x < numberOfPrimes; x++)
{
    for (int a = 2; a <= x ; ++a)
    {
        bool prime = true;
        for (int b = 2; b < a; ++b)
        {
            if (a % b == 0)
            {
                prime = false;
            }//end if
        }//end double nested for
        if (prime == true)
        {
            Console.WriteLine(a);
        }//end if
    }//end nested for
}//end for
4

7 回答 7

3

如果您查看循环结构，您应该能够很容易地看到为什么您的结果是错误的。用手穿过它们（不会花很长时间）。

您获得当前结果的原因是，并非外循环 ( x < numberOfPrimes) 的每次迭代都会产生结果 - 由于内循环的结构方式，它会跳过相当多的迭代。

你真正需要做的是重组内部循环。你最里面的循环工作正常，应该检测到任何素数。但是，您的第二个循环应该只测试尚未测试的数字。此外，一旦找到质数，它应该停止循环。

于 2010-03-10T06:55:46.410 回答
1

你应该更好地构建你的代码，你现在这样做真的很混乱。有一个方法，如果是素数IsPrime(int x)则返回真，否则返回假。x

然后，要生成numberOfPrimes素数，您可以执行以下操作：

for ( int primeCount = 0, currentPrime = 2; primeCount < numberOfPrimes; ++currentPrime )
  if ( IsPrime(currentPrime) )
  {
    // do whatever you want with currentPrime, like print it
    ++primeCount;
  }

或者使用埃拉托色尼筛，这是一种更快的方法。

要确定一个数是否为素数，请尝试它在和x之间的所有因数。为什么只有？因为 if , then和, 所以你会检查每件事两次，如果你达到甚至检查你不应该检查的东西。2Sqrt(x)Sqrt(x)a*b = xx / b = ax / a = bx / 2x

因此，如果您想使用该IsPrime(x)功能，请执行以下操作：

// i <= Sqrt(x) <=> i * i <= x
for ( int i = 2; i * i <= x; ++i )
  if ( x % i == 0 )
    return false;

return true;

但我建议你使用 Eratosthenes 的筛子，因为它要快得多。您还可以优化事物，以便您不检查偶数，因为偶数永远不是素数，除了 2（在筛子和朴素方法中）。将 x = 2 视为边缘情况，然后开始检查每隔一个数字（3、5、7、9、11 等）

于 2010-03-10T07:08:40.043 回答
0

一旦你把循环整理好，你只需要检查 b < sqrt(a) 是否更高，你就会首先找到另一个因素。

于 2010-03-10T06:57:11.320 回答
0

您正在寻找的是所谓的“埃拉托色尼筛”。因为我不喜欢做别人的家庭作业，所以这是我要给你的唯一线索。该算法在互联网上很容易找到。

于 2010-03-10T07:01:33.310 回答
0

下一个素数 (x) - 是不能被所有素数 s 整除的数，即 s<=sqrt(x)。所以你可以使用像

public bool CheckAndAddPrime(int number,List<int> primes)
{
    var sqrt = Math.Sqrt(number);
    foreach(var prime in primes)
    {
        if(prime>sqrt) break;
        if(number % prime == 0) return false;    
    }

    primes.Add(number);
    return true;
}

而且你可以得到像这样的素数

var primes = new List<int>();
Enumerable.Range(2,int.MaxValue).Where(x => x.CheckAndAddPrime(x,primes)).Take(YouCountOfPrimes);
于 2010-03-10T07:08:51.743 回答
0 
var primes = Enumerable.Range(1, numberOfPrimes )
    .Where(x => x != 1 &&
      !Enumerable.Range2, (int)Math.Sqrt(x)).Any(y => x != y && x % y == 0));

从 codethinked.com 复制

static void Main(string[] args)
{
    foreach (int no in get_first_k_primes(10))
    {
        Console.Write(" "+no.ToString() );
    }
}

public static List<int> get_first_k_primes(int k)
{
    var primes = new List<int>();

    primes.Add(2);

    int i  = 3;


    while(primes.Count < k)
    {
        if(is_prime(i))
            primes.Add(i);

        i += 2;
    }

    return primes;
}

public static bool is_prime(int n)
{
    if (n % 2 == 0 && n != 2) return false;

    int m = (int)Math.Ceiling(Math.Sqrt(n));

    for (int i = 3; i < m; i += 2)
    {
        if (n % i == 0) return false;
    }

    return true;
}
于 2010-03-10T07:11:58.033 回答
0

1. 重命名变量。

首先，如果这是家庭作业，你会得到不好的分数（如果你的老师值得他的盐），因为你有无意义的变量名（是的，甚至numberOfPrimes是错误的，应该命名requiredNumberOfPrimes。当我看到这个变量时，我问自己'这是怎么他想要多少，或者他找到了多少？'）。

其次，它将帮助您了解哪里出错了。变量应该根据它们所代表的内容进行逻辑命名。如果你不能解释你的变量代表什么（例如 a 和 b），那么你可能无法解释你在用它们做什么。

2. 看看你的循环。

for (int x = 0; x < numberOfPrimes; x++)

for 循环的结构是(initialise; 'should I continue?'; 'each loop do this'). 因此在你的循环中

  • 您将继续直到 x 等于或大于numberOfPrimes*。
  • 每次您通过循环时，您都会将 1 添加到x.

你确定这是你想做的吗？ x似乎代表您找到的素数的数量。那么，为什么不在找到素数时而不是在开始循环时增加它呢？

for (int a = 2; a <= x ; ++a)
for (int b = 2; b < a; ++b)

您正在查看 2 和x（含）之间的每个整数。对于这些整数中的每一个a，您都在查看a2 和 2 之间的每个整数。你打算用这些整数做什么？

每次循环通过顶层循环（x循环）时，您将a从头开始循环，每次循环通过a循环时，您将b从头开始循环。

所以如果x是10，你跑过一次（a=2），然后你再跑一次（a=2，a=3），然后你再跑一次（a=2，a=3，a=4 ）， 然后...

3. 收集您的结果，而不是将它们写入控制台。

var primes = new List<int>();

它是如此容易。当你找到一个素数时，primes.Add(a);. 然后您知道找到了多少个素数 ( primes.Count)，您可以使用素数列表来有效地确定下一个素数，如果需要，您可以稍后使用该列表。

于 2010-03-10T07:46:35.863 回答