1.原始算法
就是将质数的定义翻译成代码，就要看i是否能被小于它的sqrt( i )的数整除。
时间复杂度O(n*sqrt(n)) 空间复杂度O(m) m为质数个数。
2.质数筛法
①定义bool is_prime[n+1]，初始化为1（奇数为1，偶数为0）
②已经2为最小的质数，将2的倍数的布尔值都设为false，如此类推。
要注意的是最好不要把求sqrt(n)放入循环体内。
③依据is_prime数组输出相应的质数。
时间复杂度近似O(n) 空间复杂度O(n)
#include <iostream> #include <cmath> using namespace std; bool* prime_sieve(int n) { bool* p=new bool[n+1]; memset(p, 1, sizeof p); int sn=(int)sqrt((double)n); for (int i = 2; i <= sn; i++) if (p[i]) for (int j = 2*i; j <= n; j+=i) p[j] = false; return p; } void main() { int n; cin>>n; bool *primes; primes=prime_sieve(n); for(int i=2;i<=n;i++) { if (primes[i]) { cout<<i<<" "; } } cout<<endl; }
质数相关数学知识:
1.高斯猜测，n以内的素数个数大约与n/ln(n)相当，或者说，当n很大时，两者数量级相同。这就是著名的素数定理。
2.十七世纪费马猜测，2的2^n次方+1，n=0，1，2…时是素数，这样的数叫费马素数，可惜当n=5时，2^32+1就不是素数，
至今也没有找到第六个费马素数。
3.18世纪发现的最大素数是2^31-1，19世纪发现的最大素数是2^127-1，20世纪末人类已知的最大素数是2^859433-1，用十进制表示，这是一个258715位的数字。
4.孪生素数猜想：差为2的素数有无穷多对。目前知道的最大的孪生素数是1159142985×2^2304－1和1159142985×2^2304＋1。
5.歌德巴赫猜想：大于2的所有偶数均是两个素数的和，大于5的所有奇数均是三个素数之和。其中第二个猜想是第一个的自然推论，因此歌德巴赫猜想又被称为1+1问题。我国数学家陈景润证明了1+2，即所有大于2的偶数都是一个素数和只有两个素数因数的合数的和。国际上称为陈氏定理。