检查数量为素数(Check if number is prime number)

我只想问，如果这是检查的正确方式，如果数是素数或不？ 因为我读了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();
}

Answer 1:

var number;

Console.WriteLine("Accept number:");
number = Convert.ToInt32(Console.ReadLine());
if(IsPrime(number))
{
  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) ，因为在从维基百科 ，他们说：

该程序包括由每个整数米大于1且小于或等于n的平方根除以n个 。 如果这些分歧的结果是一个整数，则n不是素数，否则它是一个素数。 事实上，如果N = A * b为复合物（用a和b≠1），则因素的一个或b为一定的n至多平方根

Answer 2:

使用Soner的套路，但有轻微的变化：我们将持续到i等于Math.Ceiling(Math.Sqrt(number))这是天真的解决方案的伎俩：

boolean isPrime(int number)
{

    if (number == 1) return false;
    if (number == 2) return true;

    var limit = Math.Ceiling(Math.Sqrt(number)); //hoisting the loop limit

    for (int i = 2; i <= limit; ++i)  {
       if (number % i == 0)  return false;
    }

    return true;

}

Answer 3:

下面是这样做的一个很好的方式。

    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);
            }
        }

Answer 4:

这里有一个很好的例子 。 我丢弃代码这里以防万一的站点关闭一天。

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;
    }
}

Answer 5:

我已经实现了一个不同的方法来检查素数，因为：

• 这些解决方案大多数保留通过相同的多个迭代不必要的（例如，他们检查5，10，然后15，东西5单一％的测试）。
• 由2 A％将处理所有偶数（所有整数结束在0，2，4，6，或8）。
• 5 A％将处理的5倍数（所有整数5结束）。
• 剩下的就是在1，3结束，7或9的整数来测试连区划但好处在于我们可以通过10在时间增量，而不是由2升上去了，我将演示一个解决方案，穿出。
• 其他算法不穿出，所以他们不利用你的内核，就像我本来希望。
• 我也需要真正的大素数的支持，所以我需要使用BigInteger的数据类型，而不是INT，长等

下面是我的实现：

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;
            }
        }
    }
}

更新 ：如果你想更快速地实现与审判部门的解决方案，你可能会考虑为素数的缓存。 如果它不被其他质数均达到其平方根的值整除的数只黄金 。 除此之外，你可以考虑使用的米勒-拉宾检验的概率版本来检查数的素性，如果你正在处理的足够大的值（从罗塞塔代码的情况下所采取的网站不断下降）：

// 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;
  }
}

Answer 6:

根据@迈克尔的回答，但对于负数检查和增量计算方

    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;
    }

Answer 7:

找到这个例子在一本书，并认为这是相当完美的解决方案。

 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();
    }

Answer 8:

您还可以找到素数，直到由用户给定数的范围。

码：

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();

        }
    }

Answer 9:

这个版本如果计算平方根下面质数列表，并使用中的binarySearch的列表中找到已知的素数的素数的平方根，只有检查的列表。 我通过循环来检查第一百万素数，并花了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);
        }
    }
}

Answer 10:

这基本上是通过埃里克利珀以上地方取得了辉煌的建议的实现。

    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;
    }

Answer 11:

我认为这是对初学者一个简单的方法：

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);
        }
    }
}

Answer 12:

在该函数的算法由测试的n是否为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;
        }

Answer 13:

在该函数的算法由测试的n是否为2和SQRT（N）之间的任何整数的倍数。 如果不是，则返回TRUE，这意味着数（n）是一个素数，否则，则返回False这是指N把一个数是2的sqrt（n）的地板整数部分之间。

递归版本

        // 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;
        }

Answer 14:

素数是大于一个大而不能均匀地通过任何其他数量的，除了1和它本身分成数。

@this程序会告诉你给定数是素数或没有，会告诉你非质数，它是由（若干名），这是不是1或本身？整除@

        Console.Write("Please Enter a number: ");
        int number = int.Parse(Console.ReadLine());
        int count = 2; 
        // this is initial count number which is greater than 1

        bool prime = true;
        // used Boolean value to apply condition correctly

        int sqrtOfNumber = (int)Math.Sqrt(number); 
        // square root of input number this would help to simplify the looping.  

        while (prime && count <= sqrtOfNumber)
        {
            if ( number % count == 0)
            {
            Console.WriteLine($"{number} isn't prime and it divisible by 
                                      number {count}");  // this will generate a number isn't prime and it is divisible by a number which is rather than 1 or itself and this line will proves why it's not a prime number.
                prime = false;
            }

            count++;

        }
        if (prime && number > 1)

        {
            Console.WriteLine($"{number} is a prime number");
        }
        else if (prime == true)
        // if input is 1 or less than 1 then this code will generate
        {
            Console.WriteLine($"{number} isn't a prime");
        }

Answer 15:

我想使用的时候得到一些效率早早退出的任何（）...

    public static bool IsPrime(long n)
    {
        if (n == 1) return false;
        if (n == 3) return true;

        //Even numbers are not primes
        if (n % 2 == 0) return false;

        return !Enumerable.Range(2, Convert.ToInt32(Math.Ceiling(Math.Sqrt(n))))
            .Any(x => n % x == 0);
    }

Answer 16:

这是最简单的方式找到素数是

for(i=2; i<num; i++)
        {
            if(num%i == 0)
            {
                count++;
                break;
            }
        }
        if(count == 0)
        {
            Console.WriteLine("This is a Prime Number");
        }
        else
        {
            Console.WriteLine("This is not a Prime Number");
        }

有用的链接： https://codescracker.com/java/program/java-program-check-prime.htm

Answer 17:

   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();

Answer 18:

只有一行代码：

    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;
    }

Answer 19:

试试这个代码。

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;
    }
}

Answer 20:

你也可以试试这个：

bool isPrime(int number)
    {
        return (Enumerable.Range(1, number).Count(x => number % x == 0) == 2);
    }

文章来源: Check if number is prime number