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.使用亚里士多德筛法

• 创建一个或多个数组，这将消除您的一些 split
• 不要忘记使用数组大小​​作为其中分隔符的常见倍数
• 这可以大大加快速度
• 因为它可以通过单个数组访问消除许多 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) 的性能吗？

• 如果您需要更快的速度，请学习