素数公式

我正在尝试在C＃中编写素数函数，我想知道以下代码是否有效。 它“似乎”与前50个数字左右一起使用。 我只是想确保它无论数量有多大都能正常工作：

static bool IsPrime(int number) { if ((number == 2) || (number == 3) || (number == 5) || (number == 7) || (number == 9)) return true; if ((number % 2 != 0) && (number % 3 != 0) && (number % 5 != 0) && (number % 7 != 0) && (number % 9 != 0) && (number % 4 != 0) && (number % 6 != 0)) return true; return false; } 

Answer 1

不，它不会工作！ 尝试121 = 11 * 11 ，例如显然不是素数。

对于赋予函数的任何数，这是素数X1, X2, ..., Xn （其中n> = 2 ）的乘积，所有数都大于或等于11，您的函数将返回true。 （而且，如前所述，9不是素数）。

从维基百科您可以看到：

在数学中，素数（或素数）是一个自然数，它具有两个截然不同的自然数除数：1和它本身。

因此，检查一个数字是否为素数的一个非常简单和天真的算法可能是：

 public bool CalcIsPrime(int number) { if (number == 1) return false; if (number == 2) return true; if (number % 2 == 0) return false; // Even number for (int i = 2; i < number; i++) { // Advance from two to include correct calculation for '4' if (number % i == 0) return false; } return true; } 

有关更好的算法，请在此处查看： Primality Test

如果你想检查你的代码，请参加测试 ，这是一个用xunit编写的测试用例。

  [Theory] [MemberData(nameof(PrimeNumberTestData))] public void CalcIsPrimeTest(int number, bool expected) { Assert.Equal(expected, CalcIsPrime(number)); } public static IEnumerable PrimeNumberTestData() { yield return new object[] { 0, false }; yield return new object[] { 1, false }; yield return new object[] { 2, true }; yield return new object[] { 3, true }; yield return new object[] { 4, false }; yield return new object[] { 5, true }; yield return new object[] { 6, false }; yield return new object[] { 7, true }; yield return new object[] { 8, false }; yield return new object[] { 9, false }; yield return new object[] { 10, false }; yield return new object[] { 11, true }; yield return new object[] { 23, true }; yield return new object[] { 31, true }; yield return new object[] { 571, true }; yield return new object[] { 853, true }; yield return new object[] { 854, false }; yield return new object[] { 997, true }; yield return new object[] { 999, false }; } 

Answer 2

这必须要完成…

 public static bool IsPrime(this int number) { return (Enumerable.Range(1,number).Where(x => number % x == 0).Count() == 2); } 

Answer 3

除非if语句显式枚举0和sqrt（INT_MAX）之间的所有素数（或等效的C＃），否则这种方法肯定不会起作用。

要正确检查素数，您基本上需要尝试将您的数字除以小于其平方根的每个素数。 Eratosthenes筛选算法是您最好的选择。

Answer 4

你显然是从一个反面的维度写作，其中9是素数，所以我想我们的答案可能不适合你。 但有两件事：

1. 素数生成函数是一个非平凡但令人兴奋的事情，维基百科页面是一个很好的起点（ http://en.wikipedia.org/wiki/Formula_for_primes ）

2. 从（编号％2！= 0）开始（编号％4！= 0）。 如果你不能除以10，那么你也不能除以100。

Answer 5

原始性测试是要走的路，但是如果你想要一个快速而肮脏的黑客，这里有一些东西。

如果它的工作速度不够快，你可以围绕它构建一个类，并将PrimeNumbers集合从call到call存储起来，而不是为每次调用重新填充它。

  public bool IsPrime(int val) { Collection PrimeNumbers = new Collection(); int CheckNumber = 5; bool divisible = true; PrimeNumbers.Add(2); PrimeNumbers.Add(3); // Populating the Prime Number Collection while (CheckNumber < val) { foreach (int i in PrimeNumbers) { if (CheckNumber % i == 0) { divisible = false; break; } if (i * i > CheckNumber) { break; } } if (divisible == true) { PrimeNumbers.Add(CheckNumber); } else { divisible = true; } CheckNumber += 2; } foreach (int i in PrimeNumbers) { if (CheckNumber % i == 0) { divisible = false; break; } if (i * i > CheckNumber) { break; } } if (divisible == true) { PrimeNumbers.Add(CheckNumber); } else { divisible = true; } // Use the Prime Number Collection to determine if val is prime foreach (int i in PrimeNumbers) { if (val % i == 0) { return false; } if (i * i > val) { return true; } } // Shouldn't ever get here, but needed to build properly. return true; } 

Answer 6

您可以遵循一些基本规则来检查数字是否为素数

1. 偶数也出来了。 如果x％2 = 0，那么它不是素数
2. 所有非素数都有素数因子。 因此，您只需要针对素数测试一个数字，看看它是否有因素
3. 任何数字的最高可能因素是它的平方根。 您只需要检查值<= sqrt（number_to_check）是否可以整除。

使用该组逻辑，以下公式计算在单个线程中在C＃中生成的1,000,000个Primes：134.4164416秒。

  public IEnumerable GetPrimes(int numberPrimes) { List primes = new List { 1, 2, 3 }; long startTest = 3; while (primes.Count() < numberPrimes) { startTest += 2; bool prime = true; for (int pos = 2; pos < primes.Count() && primes[pos] <= Math.Sqrt(startTest); pos++) { if (startTest % primes[pos] == 0) { prime = false; } } if (prime) primes.Add(startTest); } return primes; } 

请记住，算法中有很多优化空间。 例如，算法可以并行化。 如果你有一个素数（假设是51），你可以测试所有数字，直到它的平方（2601），以获得单独线程中的素数，因为所有可能的素数因子都存储在列表中。

Answer 7

  static List PrimeNumbers = new List(); static void Main(string[] args) { PrimeNumbers.Add(2); PrimeNumbers.Add(3); PrimeNumbers.Add(5); PrimeNumbers.Add(7); for (long i = 11; i < 10000000; i += 2) { if (i % 5 != 0) if (IsPrime(i)) PrimeNumbers.Add(i); } } static bool IsPrime(long number) { foreach (long i in PrimeNumbers) { if (i <= Math.Sqrt(number)) { if (number % i == 0) return false; } else break; } return true; } 

Answer 8

这是一个简单的

只有奇数才是素数……所以

 static bool IsPrime(int number) { int i; if(number==2) return true; //if number is 2 then it will return prime for(i=3,i 

Answer 9

这是一个简单的代码，用于根据您的输入查找素数。

  static void Main(string[] args) { String input = Console.ReadLine(); long num = Convert.ToInt32(input); long a, b, c; c = 2; for(long i=3; i<=num; i++){ b = 0; for (long j = 2; j < i ; j++) { a = i % j; if (a != 0) { b = b+1; } else { break; } } if(b == i-2){ Console.WriteLine("{0}",i); } } Console.ReadLine(); } 

Answer 10

ExchangeCore论坛有很多代码，几乎可以让你为素数生成任何ulong数。 但基本上这里是要点：

 int primesToFind = 1000; int[] primes = new int[primesToFind]; int primesFound = 1; primes[0] = 2; for(int i = 3; i < int.MaxValue() && primesFound < primesToFind; i++) { bool isPrime = true; double sqrt = Math.sqrt(i); for(int j = 0; j 

一旦这段代码运行完毕，你的素数就会在primes数组变量中找到。

Answer 11

https://www.khanacademy.org/computing/computer-science/cryptography/comp-number-theory/a/trial-division

  public static bool isPrime(int number) { for (int k = 2; k <= Math.Ceiling(Math.Sqrt(number)); k++) { if (number > k && number % k == 0) break; if (k >= Math.Ceiling(Math.Sqrt(number)) || number == k) { return true; } } return false; } 

Answer 12

素数从0到1百万不到十分之二秒

刚完成它。 最后一次测试是0.017秒。

普通HP笔记本电脑 2.1 GHz

它变大时需要更长的时间。 对于素数1到10亿 ，我的最后一次测试是28.6897秒。 它可能在你的程序中更快，因为我正在构建类对象以获取我的参数值。

方法信息

• 使用Eratosthenes的Sieve
• 接受楼层和天花板作为参数
• 使用数组而不是列表来获得快速性能
• 根据Rosser-Schoenfeld上限初始化arrays的大小
• 分配值时，跳过2,5和7的倍数
• 最大范围介于0和2,147,483,646之间（1分44.499秒）
• 大力评论

运用

 using System; using System.Diagnostics; using System.Collections; 

方法

 private static int[] GetPrimeArray(int floor, int ceiling) { // Validate arguments. if (floor > int.MaxValue - 1) throw new ArgumentException("Floor is too high. Max: 2,147,483,646"); else if (ceiling > int.MaxValue - 1) throw new ArgumentException("Ceiling is too high. Max: 2,147,483,646"); else if (floor < 0) throw new ArgumentException("Floor must be a positive integer."); else if (ceiling < 0) throw new ArgumentException("Ceiling must be a positve integer."); else if (ceiling < floor) throw new ArgumentException("Ceiling cannot be less than floor."); // This region is only useful when testing performance. #region Performance Stopwatch sw = new Stopwatch(); sw.Start(); #endregion // Variables: int stoppingPoint = (int)Math.Sqrt(ceiling); double rosserBound = (1.25506 * (ceiling + 1)) / Math.Log(ceiling + 1, Math.E); int[] primeArray = new int[(int)rosserBound]; int primeIndex = 0; int bitIndex = 4; int innerIndex = 3; // Handle single digit prime ranges. if (ceiling < 11) { if (floor <= 2 && ceiling >= 2) // Range includes 2. primeArray[primeIndex++] = 2; if (floor <= 3 && ceiling >= 3) // Range includes 3. primeArray[primeIndex++] = 3; if (floor <= 5 && ceiling >= 5) // Range includes 5. primeArray[primeIndex++] = 5; return primeArray; } // Begin Sieve of Eratosthenes. All values initialized as true. BitArray primeBits = new BitArray(ceiling + 1, true); primeBits.Set(0, false); // Zero is not prime. primeBits.Set(1, false); // One is not prime. checked // Check overflow. { try { // Set even numbers, excluding 2, to false. for (bitIndex = 4; bitIndex < ceiling; bitIndex += 2) primeBits[bitIndex] = false; } catch { } // Break for() if overflow occurs. } // Iterate by steps of two in order to skip even values. for (bitIndex = 3; bitIndex <= stoppingPoint; bitIndex += 2) { if (primeBits[bitIndex] == true) // Is prime. { // First position to unset is always the squared value. innerIndex = bitIndex * bitIndex; primeBits[innerIndex] = false; checked // Check overflow. { try { // Set multiples of i, which are odd, to false. innerIndex += bitIndex + bitIndex; while (innerIndex <= ceiling) { primeBits[innerIndex] = false; innerIndex += bitIndex + bitIndex; } } catch { continue; } // Break while() if overflow occurs. } } } // Set initial array values. if (floor <= 2) { // Range includes 2 - 5. primeArray[primeIndex++] = 2; primeArray[primeIndex++] = 3; primeArray[primeIndex++] = 5; } else if (floor <= 3) { // Range includes 3 - 5. primeArray[primeIndex++] = 3; primeArray[primeIndex++] = 5; } else if (floor <= 5) { // Range includes 5. primeArray[primeIndex++] = 5; } // Increment values that skip multiples of 2, 3, and 5. int[] increment = { 6, 4, 2, 4, 2, 4, 6, 2 }; int indexModulus = -1; int moduloSkipAmount = (int)Math.Floor((double)(floor / 30)); // Set bit index to increment range which includes the floor. bitIndex = moduloSkipAmount * 30 + 1; // Increase bit and increment indicies until the floor is reached. for (int i = 0; i < increment.Length; i++) { if (bitIndex >= floor) break; // Floor reached. // Increment, skipping multiples of 2, 3, and 5. bitIndex += increment[++indexModulus]; } // Initialize values of return array. while (bitIndex <= ceiling) { // Add bit index to prime array, if true. if (primeBits[bitIndex]) primeArray[primeIndex++] = bitIndex; checked // Check overflow. { try { // Increment. Skip multiples of 2, 3, and 5. indexModulus = ++indexModulus % 8; bitIndex += increment[indexModulus]; } catch { break; } // Break if overflow occurs. } } // Resize array. Rosser-Schoenfeld upper bound of π(x) is not an equality. Array.Resize(ref primeArray, primeIndex); // This region is only useful when testing performance. #region Performance sw.Stop(); if (primeArray.Length == 0) Console.WriteLine("There are no prime numbers between {0} and {1}", floor, ceiling); else { Console.WriteLine(Environment.NewLine); for (int i = 0; i < primeArray.Length; i++) Console.WriteLine("{0,10}:\t\t{1,15:#,###,###,###}", i + 1, primeArray[i]); } Console.WriteLine(); Console.WriteLine("Calculation time:\t{0}", sw.Elapsed.ToString()); #endregion return primeArray; } 

欢迎评论！ 尤其是改进。

Answer 13

在这里，我们必须考虑平方根因子。 如果素数不能被任何小于任何近似数的平方根值的数除除，则可以validation素数。

 static bool isPrime(long number) { if (number == 1) return false; if (number == 2) return true; if (number % 2 == 0) return false; //Even number long nn= (long) Math.Abs(Math.Sqrt(number)); for (long i = 3; i < nn; i += 2) { if (number % i == 0) return false; } return true; }