调用函数时C++程序挂起

Question

我编写了一个代码来检查整数是否为素数,每当我调用该函数时,命令行就会挂起.我在Windows 7中使用MingW

#include<iostream>
#include<math.h>
using namespace std;
bool checkPrime(int n);
int main()
{
    int t,tempstart;
    cout<<checkPrime(6);
    return 0;
}
bool checkPrime(int n)
{
    bool check=true;
    for (int i = 0; i <(int) sqrt(n) ; i++)
    {
        if(n%i==0)
        {
            check=false;
            cout<<"asas";
            break;
        }
    }
    return check;
}

Answer 1

它不应该挂起，至少 n=6 时不应该挂起

1.试试这个

• 代替：

  if(n%i==0) 
  

• 写：

  if((n%i)==0) 
  

• 有些编译器会搞乱多操作条件，因此括号通常会有所帮助

2.如前所述，我应该从 2 开始

• n%0 被零除也许你的代码抛出隐藏的异常，这就是错误的地方

3.你尝试过调试吗？

• 在 for 循环内设置一个断点并单步执行，看看为什么当 i==2,3 时它没有停止

稍微加快速度的技巧（对于更大的 n 只需几千倍）

1.i=2,3,5,7,9,11,13,...

• 正如评论中提到的，分别执行 i=2 （通过 (n&1)==0 而不是 (n%2)==0）

• 其余的：

  for (nn=sqrt(n),i=3;i<=nn;i+=2) ...
  

2.使用半位数字代替 sqrt(n)

3.不要在for中计算sqrt（有些编译器不预先计算）

4.使用亚里士多德筛

• 创建一个或多个数组，这将消除你的一些除法
• 不要忘记使用数组大小​​作为其内部除法器的公共乘法
• 这可以大大加快速度
• 因为它可以通过单个数组访问消除许多 for 循环
• 但它需要在使用之前初始化数组

• 例如数组

  BYTE sieve[4106301>>1]; //only odd numbers are important so the size is half and each bit hold one sieve value so the size is really 4106301*8 which is divided by:
  

• 可以容纳分隔物的筛子：

• 3,5,7,11,13,17,19,23,137,131,127,113,83,61,107,101,
• 103,67,37,41,43,53,59,97,89,109,79,73,71,31,29

5.除以素数

• 您可以记住某个数组中的前 M 个素数（例如前 100 个素数）
• 并除以它们

• 和使用

  for (nn=sqrt(n),i=last prime+2;i<=nn;i++) ...
  

• 您还可以记住在某个列表中运行时计算的所有素数并使用它们

6.您可以将以上所有内容组合在一起

7.还有很多其他方法可以提高 is_prime(n) 的性能吗？

• 所以如果你需要更快的速度就研究一下