C++ 判断一个数是否为素数
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4424374/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Determining if a number is prime
提问by carla
I have perused a lot of code on this topic, but most of them produce the numbers that are prime all the way up to the input number. However, I need code which only checks whether the given input number is prime.
我已经阅读了很多关于这个主题的代码，但它们中的大多数都产生了一直到输入数字都是素数的数字。但是，我需要只检查给定输入数字是否为素数的代码。
Here is what I was able to write, but it does not work:
这是我能够写的，但它不起作用：
void primenumber(int number)
{
if(number%2!=0)
cout<<"Number is prime:"<<endl;
else
cout<<"number is NOt prime"<<endl;
}
I would appreciate if someone could give me advice on how to make this work properly.
如果有人能给我关于如何使这项工作正常工作的建议，我将不胜感激。
Update
更新
I modified it to check on all the numbers in a for loop.
我修改了它以检查 for 循环中的所有数字。
void primenumber(int number)
{
for(int i=1; i<number; i++)
{
if(number%i!=0)
cout<<"Number is prime:"<<endl;
else
cout<<"number is NOt prime"<<endl;
}
}
回答by Toomtarm Kung
bool isPrime(int number){
if(number < 2) return false;
if(number == 2) return true;
if(number % 2 == 0) return false;
for(int i=3; (i*i)<=number; i+=2){
if(number % i == 0 ) return false;
}
return true;
}
回答by LostInTheCode
My own IsPrime() function, written and based on the deterministic variant of the famous Rabin-Miller algorithm, combined with optimized step brute forcing, giving you one of the fastest prime testing functions out there.
我自己的 IsPrime() 函数是基于著名的 Rabin-Miller 算法的确定性变体编写的，结合优化的步进暴力破解，为您提供了最快的素数测试函数之一。
__int64 power(int a, int n, int mod)
{
__int64 power=a,result=1;
while(n)
{
if(n&1)
result=(result*power)%mod;
power=(power*power)%mod;
n>>=1;
}
return result;
}
bool witness(int a, int n)
{
int t,u,i;
__int64 prev,curr;
u=n/2;
t=1;
while(!(u&1))
{
u/=2;
++t;
}
prev=power(a,u,n);
for(i=1;i<=t;++i)
{
curr=(prev*prev)%n;
if((curr==1)&&(prev!=1)&&(prev!=n-1))
return true;
prev=curr;
}
if(curr!=1)
return true;
return false;
}
inline bool IsPrime( int number )
{
if ( ( (!(number & 1)) && number != 2 ) || (number < 2) || (number % 3 == 0 && number != 3) )
return (false);
if(number<1373653)
{
for( int k = 1; 36*k*k-12*k < number;++k)
if ( (number % (6*k+1) == 0) || (number % (6*k-1) == 0) )
return (false);
return true;
}
if(number < 9080191)
{
if(witness(31,number)) return false;
if(witness(73,number)) return false;
return true;
}
if(witness(2,number)) return false;
if(witness(7,number)) return false;
if(witness(61,number)) return false;
return true;
/*WARNING: Algorithm deterministic only for numbers < 4,759,123,141 (unsigned int's max is 4294967296)
if n < 1,373,653, it is enough to test a = 2 and 3.
if n < 9,080,191, it is enough to test a = 31 and 73.
if n < 4,759,123,141, it is enough to test a = 2, 7, and 61.
if n < 2,152,302,898,747, it is enough to test a = 2, 3, 5, 7, and 11.
if n < 3,474,749,660,383, it is enough to test a = 2, 3, 5, 7, 11, and 13.
if n < 341,550,071,728,321, it is enough to test a = 2, 3, 5, 7, 11, 13, and 17.*/
}
To use, copy and paste the code into the top of your program. Call it, and it returns a BOOL value, either true or false.
要使用，请将代码复制并粘贴到程序顶部。调用它，它返回一个 BOOL 值，真或假。
if(IsPrime(number))
{
cout << "It's prime";
}
else
{
cout<<"It's composite";
}
If you get a problem compiling with "__int64", replace that with "long". It compiles fine under VS2008 and VS2010.
如果您在编译“__int64”时遇到问题，请将其替换为“long”。它在 VS2008 和 VS2010 下编译得很好。
How it works: There are three parts to the function. Part checks to see if it is one of the rare exceptions (negative numbers, 1), and intercepts the running of the program.
工作原理：该函数分为三个部分。Part 检查是否是罕见的异常之一（负数，1），并拦截程序的运行。
Part two starts if the number is smaller than 1373653, which is the theoretically number where the Rabin Miller algorithm will beat my optimized brute force function. Then comes two levels of Rabin Miller, designed to minimize the number of witnesses needed. As most numbers that you'll be testing are under 4 billion, the probabilistic Rabin-Miller algorithm can be made deterministic by checking witnesses 2, 7, and 61. If you need to go over the 4 billion cap, you will need a large number library, and apply a modulus or bit shift modification to the power() function.
如果数字小于 1373653，则第二部分开始，这是 Rabin Miller 算法将击败我优化的蛮力函数的理论数字。然后是两个级别的 Rabin Miller，旨在最大限度地减少所需的证人数量。由于您要测试的大多数数字都在 40 亿以下，因此可以通过检查证人 2、7 和 61 使概率 Rabin-Miller 算法具有确定性。如果您需要超过 40 亿的上限，则需要一个大的number 库，并对 power() 函数应用模数或位移修改。
If you insist on a brute force method, here is just my optimized brute force IsPrime() function:
如果你坚持使用蛮力方法，这里只是我优化后的蛮力 IsPrime() 函数：
inline bool IsPrime( int number )
{
if ( ( (!(number & 1)) && number != 2 ) || (number < 2) || (number % 3 == 0 && number != 3) )
return (false);
for( int k = 1; 36*k*k-12*k < number;++k)
if ( (number % (6*k+1) == 0) || (number % (6*k-1) == 0) )
return (false);
return true;
}
}
How this brute force piece works: All prime numbers (except 2 and 3) can be expressed in the form 6k+1 or 6k-1, where k is a positive whole number. This code uses this fact, and tests all numbers in the form of 6k+1 or 6k-1 less than the square root of the number in question. This piece is integrated into my larger IsPrime() function (the function shown first).
这个蛮力块是如何工作的：所有素数（除了 2 和 3）都可以用 6k+1 或 6k-1 的形式表示，其中 k 是一个正整数。此代码使用此事实，并以小于所讨论数字的平方根的 6k+1 或 6k-1 的形式测试所有数字。这部分集成到我更大的 IsPrime() 函数中（首先显示的函数）。
If you need to find all the prime numbers below a number, find all the prime numbers below 1000, look into the Sieve of Eratosthenes. Another favorite of mine.
如果你需要找出一个数以下的所有质数，找出 1000 以下的所有质数，看看 Eratosthenes 的筛子。我的另一个最爱。
As an additional note, I would love to see anyone implement the Eliptical Curve Method algorithm, been wanting to see that implemented in C++ for a while now, I lost my implementation of it. Theoretically, it's even faster than the deterministic Rabin Miller algorithm I implemented, although I'm not sure if that's true for numbers under 4 billion.
作为附加说明，我很想看到任何人实现椭圆曲线方法算法，一段时间以来一直希望看到用 C++ 实现，但我丢失了它的实现。从理论上讲，它甚至比我实现的确定性 Rabin Miller 算法还要快，尽管我不确定对于 40 亿以下的数字是否如此。
回答by Pablo Santa Cruz
You need to do some more checking. Right now, you are only checking if the number is divisible by 2. Do the same for 2, 3, 4, 5, 6, ... up to number. Hint: use a loop.
你需要做更多的检查。现在，您只检查数字是否可以被 2 整除。对 2, 3, 4, 5, 6, ... 执行相同的操作，直到number. 提示：使用循环。
After you resolve this, try looking for optimizations. Hint: You only have to check all numbers up to the square root of the number
解决此问题后，请尝试寻找优化。提示：你只需要检查所有数字直到数字的平方根
回答by Valentin Kuzub
I would guess taking sqrt and running foreach frpm 2 to sqrt+1 if(input% number!=0) return false; once you reach sqrt+1 you can be sure its prime.
我猜想使用 sqrt 并运行 foreach frpm 2 to sqrt+1 if(input% number!=0) return false; 一旦你达到 sqrt+1，你就可以确定它是最好的。
回答by user470379
If you know the range of the inputs (which you do since your function takes an int), you can precompute a table of primes less than or equal to the square root of the max input (2^31-1 in this case), and then test for divisibility by each prime in the table less than or equal to the square root of the number given.
如果您知道输入的范围（您这样做是因为您的函数采用int），您可以预先计算一个小于或等于最大输入平方根的素数表（在本例中为 2^31-1），并且然后测试表中每个小于或等于给定数字的平方根的素数的整除性。
回答by un33k
C++
C++
bool isPrime(int number){
if (number != 2){
if (number < 2 || number % 2 == 0) {
return false;
}
for(int i=3; (i*i)<=number; i+=2){
if(number % i == 0 ){
return false;
}
}
}
return true;
}
Javascript
Javascript
function isPrime(number)
{
if (number !== 2) {
if (number < 2 || number % 2 === 0) {
return false;
}
for (var i=3; (i*i)<=number; i+=2)
{
if (number % 2 === 0){
return false;
}
}
}
return true;
}
Python
Python
def isPrime(number):
if (number != 2):
if (number < 2 or number % 2 == 0):
return False
i = 3
while (i*i) <= number:
if(number % i == 0 ):
return False;
i += 2
return True;
回答by user6449382
bool check_prime(int num) {
for (int i = num - 1; i > 1; i--) {
if ((num % i) == 0)
return false;
}
return true;
}
checks for any number if its a prime number
检查任何数字，如果它是质数
回答by Dev Kumar
Use mathematics first find square root of number then start loop till the number ends which you get after square rooting. check for each value whether the given number is divisible by the iterating value .if any value divides the given number then it is not a prime number otherwise prime. Here is the code
使用数学首先找到数字的平方根，然后开始循环，直到平方根后得到的数字结束。检查每个值是否给定数字可被迭代值整除。如果任何值将给定数字整除，则它不是素数，否则为素数。这是代码
bool is_Prime(int n)
{
int square_root = sqrt(n); // use math.h
int toggle = 1;
for(int i = 2; i <= square_root; i++)
{
if(n%i==0)
{
toggle = 0;
break;
}
}
if(toggle)
return true;
else
return false;
}
回答by Michael Koval
This code only checks if the number is divisible by two. For a number to be prime, it must not be evenly divisible by all integers less than itself. This can be naively implemented by checking if it is divisible by all integers less than floor(sqrt(n))in a loop. If you are interested, there are a number of much faster algorithmsin existence.
此代码仅检查数字是否可被 2 整除。对于素数，它不能被所有小于它的整数整除。这可以通过检查它是否可以被所有小于floor(sqrt(n))循环的整数整除来天真地实现。如果您有兴趣，现在有许多更快的算法。
回答by karatedog
If you are lazy, and have a lot of RAM, create a sieve of Eratostheneswhich is practically a giant array from which you kicked all numbers that are not prime. From then on every prime "probability" test will be super quick. The upper limit for this solution for fast results is the amount of you RAM. The upper limit for this solution for superslow results is your hard disk's capacity.
如果您很懒惰，并且有很多 RAM，请创建一个Eratosthenes 筛子，它实际上是一个巨大的数组，您可以从中踢出所有非质数的数字。从那时起，每个素数“概率”测试都将非常快速。此解决方案快速结果的上限是您的 RAM 量。这种超慢结果解决方案的上限是您的硬盘容量。
