我想问一下这是否是检查数字是否为素数的正确方法？因为我读到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 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)，因为在wikipedia，他们说：
该例程包括将n除以每个整数m，该整数m大于1且小于或等于n的平方根。如果任何这些除法的结果是整数，则n不是素数，否则它是素数。实际上，如果n = a * b是复合的（a和b≠1）那么因子a或b之一必然至多为n的平方根
这基本上是由Eric Lippert在上面提出的一个很好的建议的实现。
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;
}
我认为这对初学者来说是一种简单的方法：
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);
}
}
}
该函数中的算法包括测试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;
}
该函数中的算法包括测试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;
}
素数是大于1的数字，除了1和它本身之外，不能被任何其他数字均分。
@这个程序会告诉你给定的数字是否为素数，并且会显示非素数，它可以被（一个数字）整除而不是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");
}
当我使用Any（）时，我试图从早期退出中获得一些效率...
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);
}
这是查找素数的最简单方法
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
这是一个没有其他答案的“混乱”的版本，只是诀窍。
static void Main(string[] args)
{
Console.WriteLine("Enter your number: ");
int num = Convert.ToInt32(Console.ReadLine());
bool isPrime = true;
for (int i = 2; i < num/2; i++)
{
if (num % i == 0)
{
isPrime = false;
break;
}
}
if (isPrime)
Console.WriteLine("It is Prime");
else
Console.WriteLine("It is not Prime");
Console.ReadLine();
}
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;
}
使用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;
}
试试这个代码。
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;
}
}
你也可以试试这个：
bool isPrime(int number)
{
return (Enumerable.Range(1, number).Count(x => number % x == 0) == 2);
}
这是一个很好的方法。
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);
}
}
这是一个good example。我正在放弃这里的代码，以防万一网站出现故障。
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;
}
}
我已经实现了一种不同的方法来检查质数，因为：
这是我的实现：
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;
}
}
}
}
更新：如果您想更快地实现试验分区的解决方案，您可能会考虑使用素数缓存。如果数字不能被其平方根值达到的其他素数整除，则该数字仅为素数。除此之外，您可以考虑使用the probabilistic version of the Miller-Rabin primality test来检查数字的素数，如果您正在处理足够大的值（如果站点出现故障，则从Rosetta Code中获取）：
// 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;
}
在一本书中找到这个例子，并认为这是一个非常优雅的解决方案。
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();
}
您还可以找到用户直到给定数量的素数范围。
码：
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();
}
}
此版本计算素数平方根列表，仅检查平方根下面的素数列表，并使用列表中的二进制搜索来查找已知素数。我循环检查前1,000,000个素数，花了大约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);
}
}
}