确定数字是否为素数

Question

我已经在这个主题上仔细阅读了很多代码,但是大多数代码都生成了一直到输入数字为止的数字.但是,我需要的代码只检查给定的输入数是否为素数.

这是我能够写的,但它不起作用:

void primenumber(int number)
{
    if(number%2!=0)
      cout<<"Number is prime:"<<endl;
    else 
      cout<<"number is NOt prime"<<endl;
}

如果有人能就如何正确地开展这项工作给我建议,我将不胜感激.

更新

我修改它来检查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;
    }  
}

Answer 1

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;

}

Answer 2

我自己的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.*/
}

要使用,复制并粘贴代码到程序的顶部.调用它,它返回一个BOOL值,无论是true还是false.

if(IsPrime(number))
{
    cout << "It's prime";
}

else
{
    cout<<"It's composite";
}

如果您在使用"__int64"进行编译时出现问题,请将其替换为"long".它在VS2008和VS2010下编译得很好.

工作原理:该功能有三个部分.部分检查它是否是极少数例外(负数,1)之一,并拦截程序的运行.

如果数字小于1373653,则第二部分开始,这是理论上Rabin Miller算法将击败我的优化强力函数的数字.接下来是两个级别的拉宾米勒,旨在尽量减少所需证人的数量.由于您将要测试的大多数数字都在40亿以下,因此通过检查目击者2,7和61可以使概率性Rabin-Miller算法具有确定性.如果您需要超过40亿个上限,则需要大量数字库,并对power()函数应用模数或位移修改.

如果你坚持使用强力方法,这里只是我优化的强力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;
 }
}

这个强力部分是如何工作的:所有素数(2和3除外)都可以用6k + 1或6k-1的形式表示,其中k是正整数.此代码使用此事实,并以比所讨论数字的平方根小6k + 1或6k-1的形式测试所有数字.这件作品已集成到我的大型IsPrime()函数中(首先显示的功能).

如果你需要找到一个数字下方的所有素数,找到1000以下的所有素数,请查看Eratosthenes的Sieve.我的另一个最爱.

另外需要注意的是,我很乐意看到有人实现Eliptical Curve Method算法,一直希望看到用C++实现一段时间,我失去了它的实现.从理论上讲,它甚至比我实施的确定性Rabin Miller算法更快,尽管我不确定这对40亿以下的数字是否正确.

Answer 3

你需要做更多的检查.现在,你只是检查这个数字是否可以被2整除.对于2,3,4,5,6 ......最多相同number.提示:使用循环.

解决此问题后,请尝试查找优化.提示:您只需要检查所有数字,直到数字的平方根

Answer 4

如果(输入%number!= 0)返回false,我猜想将sqrt和foreach frpm 2运行到sqrt + 1; 一旦达到sqrt + 1,你就可以确定它的最佳状态.

Answer 5

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

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

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;