面试题1到n的质数和

Question

我今天去出了这个题：从1到n的质数和
要求写出一个算法请高人帮我看看

Answer 1

using System;class PrimesSum
{
  static void Main()
  {
    int n = 100;
    int sum = 2;
    for (int i = 1; i <= n; i += 2)
    {
      if (IsPrime(i)) sum += i;
    }
    Console.WriteLine(sum);
  }
  
  static bool IsPrime(int x)
  {
    if (x < 2 || x % 2 == 0) return false;
    if (x == 2) return true;
    for (int i = 3; i <= Math.Sqrt(x); i += 2)
    {
      if (x % i == 0) return false;
    }
    return true;
  }
}

Answer 2

  static bool IsPrime(int x)
  {
    if (x == 2) return true;
    if (x < 2 || x % 2 == 0) return false;
    for (int i = 3; i <= Math.Sqrt(x); i += 2)
    {
      if (x % i == 0) return false;
    }
    return true;
  }
sorry,
    if (x < 2 || x % 2 == 0) return false;
    if (x == 2) return true;这两行应该对调一下位置。

Answer 3

谢谢 wuyi8808 回复这个能用递归吗？

Answer 4

应该是用循环，没看出来可以用递归的地方。难道是在 IsPrime() 中用递归？恐怕会更慢。

Answer 5

  static bool IsPrime(int x)
  {
    if (x == 2) return true;
    if (x < 2 || x % 2 == 0) return false;
    for (int i = 3; i <= Math.Sqrt(x); i += 2)
    {
      if (IsPrime(i) && x % i == 0) return false;
    }
    return true;
  }这就是用递归的版本。注意这行：      if (IsPrime(i) && x % i == 0) return false;IsPrime() 中调用了 IsPrime() 本身。但是我怀疑会更慢，没有实际测试过，有兴趣你可以自己测试下。

Answer 6

这样也行(可能更快)：using System;
using System.Collections.Generic;class PrimesSum
{
  static List<int> primes = new List<int>();  static void Main()
  {
    int n = 100;
    int sum = 2;
    for (int i = 1; i <= n; i += 2)
    {
      if (IsPrime(i)) sum += i;
    }
    Console.WriteLine(sum);
  }
  
  static bool IsPrime(int x)
  {
    if (x == 2) return true;
    if (x < 2 || x % 2 == 0) return false;
    foreach (int i in primes)
    {
      if (i > Math.Sqrt(x)) break; // 这行可要可不要，不影响结果。
      if (x % i == 0) return false;
    }
    primes.Add(x);
    return true;
  }
}