锐客网

  1. 首页 > it技术 > >

C语言算法|判断素数方法总结

c语言算法C语言算法

time命令输出的信息

[1] real : 表示程序整个的运行耗时。可以理解为foo运行开始时刻你看了一下手表，程序运行结束时，你又看了一下手表，两次时间的差值就是本次real 代表的值
[2]user ：这个时间代表的是foo运行在用户态的cpu时间，什么意思？
首先，我来讲一下用户态和核心态：
核心态（Kernel Mode）：
在内核态，代码拥有完全的，不受任何限制的访问底层硬件的能力。可以执行任意的CPU指令，访问任意的内存地址。内核态通常情况下都是为那些最底层的，由操作系统提供的，可信可靠的代码来运行的。内核态的代码崩溃将是灾难性的，它会影响到整个系统。
—– In Kernel mode, the executing code has complete and unrestricted access to the underlying hardware. It can execute any CPU instruction and reference any memory address. Kernel mode is generally reserved for the lowest-level, most trusted functions of the operating system. Crashes in kernel mode are catastrophic; they will halt the entire PC.
用户态（User Mode）：
在用户态，代码不具备直接访问硬件或者访问内存的能力，而必须借助操作系统提供的可靠的、底层的API来访问硬件或者内存。由于这种隔离带来的保护作用，用户态的代码崩溃（Crash），系统是可以恢复的。我们大多数的代码都是运行在用户态的。
—– In User mode, the executing code has no ability to directly access hardware or reference memory. Code running in user mode must delegate to system APIs to access hardware or memory. Due to the protection afforded by this sort of isolation, crashes in user mode are always recoverable. Most of the code running on your computer will execute in user mode.
为什么要区分Kernel Mode 和 User Mode呢？答案是隔离保护，使得系统更稳定。
好，讲完用户态和核心态之后，我们来看user time。我们已经说过了，这个指的是程序foo运行在用户态的cpu时间，cpu时间不是墙上的钟走过的时间，而是指CPU工作时间。
sys : 这个时间代表的是foo运行在核心态的cpu时间
1.根据素数的定义
即只能被1或者自身整除的自然数（不包括1），称为素数/质数。
#include using namespace std; #define MAX 10000 bool IsPrime(int n) { if(n == 1) return false; for(int i=2; i

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
统计耗时
C语言算法|判断素数方法总结
文章图片

2.利用定理
如果一个数是素数，那么它的最小质因数肯定<=它的开方.例如，50，最小质因数为2，2<50的开方。
不是合数，那就是素数。根据上面的定理，一个数只要能被比他的开方<=的所有数整除，那它肯定是合数；反之为素数。这样遍历的数量就会相应减少很多。
#include #include using namespace std; #define MAX 10000 bool IsPrime(int n) { int Sqtmp = sqrt(n); if(n == 1) return false; for(int i=2; i<=Sqtmp; ++i) { if(n%i == 0) return false; } return true; } int main(int argc, char const* argv[]) { int n = 0; while(n++ < MAX) { if(IsPrime(n)) cout<

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
统计耗时
C语言算法|判断素数方法总结
文章图片

3.筛法求质数。
这种方法高效，但内存消耗较大。

用筛法求素数的基本思想是：把从1开始的、某一范围内的正整数从小到大顺序排列， 1不是素数，首先把它筛掉。剩下的数中选择最小的数是素数，然后去掉它的倍数。依次类推，直到筛子为空时结束。




【C语言算法|判断素数方法总结】

转 https://blog.csdn.net/derkampf/article/details/62898513

    推荐阅读


    上一篇：Docker学习(三)-Docker相关工具

    下一篇：《超脱》观后感（绝望压抑的生活）