检查号码是否是素数
我只想问一下，如果这是检查数字是否为素数的正确方法？ 因为我读了0和1不是素数。
int num1; Console.WriteLine("Accept number:"); num1 = Convert.ToInt32(Console.ReadLine()); if (num1 == 0 || num1 == 1) { Console.WriteLine(num1 + " is not prime number"); Console.ReadLine(); } else { for (int a = 2; a <= num1 / 2; a++) { if (num1 % a == 0) { Console.WriteLine(num1 + " is not prime number"); return; } } Console.WriteLine(num1 + " is a prime number"); Console.ReadLine(); } var num1; Console.WriteLine("Accept number:"); num1 = Convert.ToInt32(Console.ReadLine()); if(IsPrime(num1)) { Console.WriteLine("It is prime"); } else { Console.WriteLine("It is not prime"); } public static bool IsPrime(int number) { if (number == 1) return false; if (number == 2) return true; if (number % 2 == 0) return false; var boundary = (int)Math.Floor(Math.Sqrt(number)); for (int i = 3; i <= boundary; i+=2) { if (number % i == 0) return false; } return true; }
我将number / 2更改为Math.Sqrt(number)因为在wikipedia中 ，他们说：
这个例程由n除以每个大于1且小于或等于n的平方根的整数m组成。 如果这些划分的结果是整数，那么n不是素数，否则就是素数。 事实上，如果n = a * b是复合的（a和b≠1），那么因子a或b中的一个至多必须是n的平方根
使用Soner代码：
运行，直到i等于Math.Ceiling(Math.Sqrt(number))这是诀窍
boolean isPrime(int number) { if (number == 1) return false; if (number == 2) return true; for (int i = 2; i <= Math.Ceiling(Math.Sqrt(number)); ++i) { if (number % i == 0) return false; } return true; }
这是一个很好的方法。
static bool IsPrime(int n) { if (n > 1) { return Enumerable.Range(1, n).Where(x => n%x == 0) .SequenceEqual(new[] {1, n}); } return false; }
编写程序的快速方法是：
for (;;) { Console.Write("Accept number: "); int n = int.Parse(Console.ReadLine()); if (IsPrime(n)) { Console.WriteLine("{0} is a prime number",n); } else { Console.WriteLine("{0} is not a prime number",n); } }
这是一个很好的例子 。 我将代码放在这里，以防万一网站出现故障。
using System; class Program { static void Main() { // // Write prime numbers between 0 and 100. // Console.WriteLine("--- Primes between 0 and 100 ---"); for (int i = 0; i < 100; i++) { bool prime = PrimeTool.IsPrime(i); if (prime) { Console.Write("Prime: "); Console.WriteLine(i); } } // // Write prime numbers between 10000 and 10100 // Console.WriteLine("--- Primes between 10000 and 10100 ---"); for (int i = 10000; i < 10100; i++) { if (PrimeTool.IsPrime(i)) { Console.Write("Prime: "); Console.WriteLine(i); } } } }
这是包含IsPrime方法的类：
using System; public static class PrimeTool { public static bool IsPrime(int candidate) { // Test whether the parameter is a prime number. if ((candidate & 1) == 0) { if (candidate == 2) { return true; } else { return false; } } // Note: // ... This version was changed to test the square. // ... Original version tested against the square root. // ... Also we exclude 1 at the end. for (int i = 3; (i * i) <= candidate; i += 2) { if ((candidate % i) == 0) { return false; } } return candidate != 1; } }
我已经实现了一个不同的方法来检查素数，因为：
- 大多数这些解决scheme不断地迭代通过相同的多个不必要的（例如，他们检查5,10和15，一个单一的5％将testing）。
- 一个％2将处理所有偶数（所有以0,2,4,6或8结尾的整数）。
- 一个5乘以5将处理所有5的倍数（所有以5结尾的整数）。
- 剩下的就是用1,3,7或9的整数来testing均匀分割。但是美的是，我们可以一次增加10，而不是增加2，我将演示一个解决scheme，即拧出。
- 其他的algorithm没有被穿透，所以他们没有像我所希望的那样利用你的内核。
- 我还需要支持非常大的素数，所以我需要使用BigInteger数据types而不是int，long等。
这是我的实现：
public static BigInteger IntegerSquareRoot(BigInteger value) { if (value > 0) { int bitLength = value.ToByteArray().Length * 8; BigInteger root = BigInteger.One << (bitLength / 2); while (!IsSquareRoot(value, root)) { root += value / root; root /= 2; } return root; } else return 0; } private static Boolean IsSquareRoot(BigInteger n, BigInteger root) { BigInteger lowerBound = root * root; BigInteger upperBound = (root + 1) * (root + 1); return (n >= lowerBound && n < upperBound); } static bool IsPrime(BigInteger value) { Console.WriteLine("Checking if {0} is a prime number.", value); if (value < 3) { if (value == 2) { Console.WriteLine("{0} is a prime number.", value); return true; } else { Console.WriteLine("{0} is not a prime number because it is below 2.", value); return false; } } else { if (value % 2 == 0) { Console.WriteLine("{0} is not a prime number because it is divisible by 2.", value); return false; } else if (value == 5) { Console.WriteLine("{0} is a prime number.", value); return true; } else if (value % 5 == 0) { Console.WriteLine("{0} is not a prime number because it is divisible by 5.", value); return false; } else { // The only way this number is a prime number at this point is if it is divisible by numbers ending with 1, 3, 7, and 9. AutoResetEvent success = new AutoResetEvent(false); AutoResetEvent failure = new AutoResetEvent(false); AutoResetEvent onesSucceeded = new AutoResetEvent(false); AutoResetEvent threesSucceeded = new AutoResetEvent(false); AutoResetEvent sevensSucceeded = new AutoResetEvent(false); AutoResetEvent ninesSucceeded = new AutoResetEvent(false); BigInteger squareRootedValue = IntegerSquareRoot(value); Thread ones = new Thread(() => { for (BigInteger i = 11; i <= squareRootedValue; i += 10) { if (value % i == 0) { Console.WriteLine("{0} is not a prime number because it is divisible by {1}.", value, i); failure.Set(); } } onesSucceeded.Set(); }); ones.Start(); Thread threes = new Thread(() => { for (BigInteger i = 3; i <= squareRootedValue; i += 10) { if (value % i == 0) { Console.WriteLine("{0} is not a prime number because it is divisible by {1}.", value, i); failure.Set(); } } threesSucceeded.Set(); }); threes.Start(); Thread sevens = new Thread(() => { for (BigInteger i = 7; i <= squareRootedValue; i += 10) { if (value % i == 0) { Console.WriteLine("{0} is not a prime number because it is divisible by {1}.", value, i); failure.Set(); } } sevensSucceeded.Set(); }); sevens.Start(); Thread nines = new Thread(() => { for (BigInteger i = 9; i <= squareRootedValue; i += 10) { if (value % i == 0) { Console.WriteLine("{0} is not a prime number because it is divisible by {1}.", value, i); failure.Set(); } } ninesSucceeded.Set(); }); nines.Start(); Thread successWaiter = new Thread(() => { AutoResetEvent.WaitAll(new WaitHandle[] { onesSucceeded, threesSucceeded, sevensSucceeded, ninesSucceeded }); success.Set(); }); successWaiter.Start(); int result = AutoResetEvent.WaitAny(new WaitHandle[] { success, failure }); try { successWaiter.Abort(); } catch { } try { ones.Abort(); } catch { } try { threes.Abort(); } catch { } try { sevens.Abort(); } catch { } try { nines.Abort(); } catch { } if (result == 1) { return false; } else { Console.WriteLine("{0} is a prime number.", value); return true; } } } }
更新 ：如果您想更快速地实施试用版解决scheme，则可以考虑使用素数caching。 一个数字只有在素数不能被其他素数整除的情况下，才能被其平方根的值所整除 。 除此之外，如果你正在处理足够大的值（如果网站有故障，则从Rosetta Code中获取），你可以考虑使用Miller-Rabin素数检验的概率版本来检查一个数字的素数：
// Miller-Rabin primality test as an extension method on the BigInteger type. // Based on the Ruby implementation on this page. public static class BigIntegerExtensions { public static bool IsProbablePrime(this BigInteger source, int certainty) { if(source == 2 || source == 3) return true; if(source < 2 || source % 2 == 0) return false; BigInteger d = source - 1; int s = 0; while(d % 2 == 0) { d /= 2; s += 1; } // There is no built-in method for generating random BigInteger values. // Instead, random BigIntegers are constructed from randomly generated // byte arrays of the same length as the source. RandomNumberGenerator rng = RandomNumberGenerator.Create(); byte[] bytes = new byte[source.ToByteArray().LongLength]; BigInteger a; for(int i = 0; i < certainty; i++) { do { // This may raise an exception in Mono 2.10.8 and earlier. // http://bugzilla.xamarin.com/show_bug.cgi?id=2761 rng.GetBytes(bytes); a = new BigInteger(bytes); } while(a < 2 || a >= source - 2); BigInteger x = BigInteger.ModPow(a, d, source); if(x == 1 || x == source - 1) continue; for(int r = 1; r < s; r++) { x = BigInteger.ModPow(x, 2, source); if(x == 1) return false; if(x == source - 1) break; } if(x != source - 1) return false; } return true; } }
基于@ Micheal的答案，但检查负数，并逐渐计算平方
public static bool IsPrime( int candidate ) { if ( candidate % 2 <= 0 ) { return candidate == 2; } int power2 = 9; for ( int divisor = 3; power2 <= candidate; divisor += 2 ) { if ( candidate % divisor == 0 ) return false; power2 += divisor * 4 + 4; } return true; }
在一本书中find这个例子，并认为这是相当优雅的解决scheme。
static void Main(string[] args) { Console.Write("Enter a number: "); int theNum = int.Parse(Console.ReadLine()); if (theNum < 3) // special case check, less than 3 { if (theNum == 2) { // The only positive number that is a prime Console.WriteLine("{0} is a prime!", theNum); } else { // All others, including 1 and all negative numbers, // are not primes Console.WriteLine("{0} is not a prime", theNum); } } else { if (theNum % 2 == 0) { // Is the number even? If yes it cannot be a prime Console.WriteLine("{0} is not a prime", theNum); } else { // If number is odd, it could be a prime int div; // This loop starts and 3 and does a modulo operation on all // numbers. As soon as there is no remainder, the loop stops. // This can be true under only two circumstances: The value of // div becomes equal to theNum, or theNum is divided evenly by // another value. for (div = 3; theNum % div != 0; div += 2) ; // do nothing if (div == theNum) { // if theNum and div are equal it must be a prime Console.WriteLine("{0} is a prime!", theNum); } else { // some other number divided evenly into theNum, and it is not // itself, so it is not a prime Console.WriteLine("{0} is not a prime", theNum); } } } Console.ReadLine(); }
你也可以find一系列的质数，直到用户给定的数字。
码：
class Program { static void Main(string[] args) { Console.WriteLine("Input a number to find Prime numbers\n"); int inp = Convert.ToInt32(Console.ReadLine()); Console.WriteLine("\n Prime Numbers are:\n------------------------------"); int count = 0; for (int i = 1; i <= inp; i++) { for (int j = 2; j < i; j++) // j=2 because if we divide any number with 1 the remaider will always 0, so skip this step to minimize time duration. { if (i % j != 0) { count += 1; } } if (count == (i - 2)) { Console.Write(i + "\t"); } count = 0; } Console.ReadKey(); } }
该版本计算质数平方根的列表，并只检查平方根以下的素数列表，并使用列表中的二元search来查找已知的素数。 我循环检查了第一百万个素数，耗时约7秒。
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace ConsoleApplication5 { class Program { static void Main(string[] args) { //test(); testMax(); Console.ReadLine(); } static void testMax() { List<int> CheckPrimes = Enumerable.Range(2, 1000000).ToList(); PrimeChecker pc = new PrimeChecker(1000000); foreach (int i in CheckPrimes) { if (pc.isPrime(i)) { Console.WriteLine(i); } } } } public class PrimeChecker{ public List<int> KnownRootPrimesList; public int HighestKnownPrime = 3; public PrimeChecker(int Max=1000000){ KnownRootPrimesList = new List<int>(); KnownRootPrimesList.Add(2); KnownRootPrimesList.Add(3); isPrime(Max); } public bool isPrime(int value) { int srt = Convert.ToInt32(Math.Ceiling(Math.Sqrt(Convert.ToDouble(value)))); if(srt > HighestKnownPrime) { for(int i = HighestKnownPrime + 1; i <= srt; i++) { if (i > HighestKnownPrime) { if(isPrimeCalculation(i)) { KnownRootPrimesList.Add(i); HighestKnownPrime = i; } } } } bool isValuePrime = isPrimeCalculation(value); return(isValuePrime); } private bool isPrimeCalculation(int value) { if (value < HighestKnownPrime) { if (KnownRootPrimesList.BinarySearch(value) > -1) { return (true); } else { return (false); } } int srt = Convert.ToInt32(Math.Ceiling(Math.Sqrt(Convert.ToDouble(value)))); bool isPrime = true; List<int> CheckList = KnownRootPrimesList.ToList(); if (HighestKnownPrime + 1 < srt) { CheckList.AddRange(Enumerable.Range(HighestKnownPrime + 1, srt)); } foreach(int i in CheckList) { isPrime = ((value % i) != 0); if(!isPrime) { break; } } return (isPrime); } public bool isPrimeStandard(int value) { int srt = Convert.ToInt32(Math.Ceiling(Math.Sqrt(Convert.ToDouble(value)))); bool isPrime = true; List<int> CheckList = Enumerable.Range(2, srt).ToList(); foreach (int i in CheckList) { isPrime = ((value % i) != 0); if (!isPrime) { break; } } return (isPrime); } } }
我认为这对于初学者来说是一个简单的方法：
using System; using System.Numerics; public class PrimeChecker { public static void Main() { // Input Console.WriteLine("Enter number to check is it prime: "); BigInteger n = BigInteger.Parse(Console.ReadLine()); bool prime = false; // Logic if ( n==0 || n==1) { Console.WriteLine(prime); } else if ( n==2 ) { prime = true; Console.WriteLine(prime); } else if (n>2) { IsPrime(n, prime); } } // Method public static void IsPrime(BigInteger n, bool prime) { bool local = false; for (int i=2; i<=(BigInteger)Math.Sqrt((double)n); i++) { if (n % i == 0) { local = true; break; } } if (local) { Console.WriteLine(prime); } else { prime = true; Console.WriteLine(prime); } } }
这基本上是Eric Lippert在上面提出的一个很好的build议。
public static bool isPrime(int number) { if (number == 1) return false; if (number == 2 || number == 3 || number == 5) return true; if (number % 2 == 0 || number % 3 == 0 || number % 5 == 0) return false; var boundary = (int)Math.Floor(Math.Sqrt(number)); // You can do less work by observing that at this point, all primes // other than 2 and 3 leave a remainder of either 1 or 5 when divided by 6. // The other possible remainders have been taken care of. int i = 6; // start from 6, since others below have been handled. while (i <= boundary) { if (number % (i + 1) == 0 || number % (i + 5) == 0) return false; i += 6; } return true; }
函数中的algorithm包括testingn是否是2和sqrt（n）之间的任意整数的倍数。 如果不是，则返回True，这意味着数字（n）是素数，否则返回False，这意味着n将数字与2和sqrt（n）的整数部分之间的数字相除。
private static bool isPrime(int n) { int k = 2; while (k * k <= n) { if ((n % k) == 0) return false; else k++; } return true; }
函数中的algorithm包括testingn是否是2和sqrt（n）之间的整数倍数。 如果不是，则返回True，这意味着数字（n）是素数，否则返回False，这意味着n将数字与2和sqrt（n）的整数部分之间的数字相除。
recursion版本
// Always call it as isPrime(n,2) private static bool isPrime(int n, int k) { if (k * k <= n) { if ((n % k) == 0) return false; else return isPrime(n, k + 1); } else return true; }
你也可以试试这个：
bool isPrime(int number) { return (Enumerable.Range(1, number).Count(x => number % x == 0) == 2); }
bool flag = false; for (int n = 1;n < 101;n++) { if (n == 1 || n == 2) { Console.WriteLine("prime"); } else { for (int i = 2; i < n; i++) { if (n % i == 0) { flag = true; break; } } } if (flag) { Console.WriteLine(n+" not prime"); } else { Console.WriteLine(n + " prime"); } flag = false; } Console.ReadLine();
只有一行代码：
private static bool primeNumberTest(int i) { return i > 3 ? ( (Enumerable.Range(2, (i / 2) + 1).Where(x => (i % x == 0))).Count() > 0 ? false : true ) : i == 2 || i == 3 ? true : false; }
试试这个代码。
bool isPrimeNubmer(int n) { if (n == 2 || n == 3) //2, 3 are prime numbers return true; else if (n % 2 == 0) //even numbers are not prime numbers return false; else { int j = 3; int k = (n + 1) / 2 ; while (j <= k) { if (n % j == 0) return false; j = j + 2; } return true; } }
