[关闭]
@songpfei 2016-05-17T20:03:31.000000Z 字数 1210 阅读 1652

素数判断

OJ_算法


素数判断方法:

 问题:求出所有小于等于n的素数

方法1:

原理:一个数 n 如果是合数,那么它的所有的因子不超过sqrt(n)--n的开方;
方案:使用循环解决;
时间复杂度:o(n*sqrt(n))
当n很大时很耗时;

  1. void PrimeNumber(int n, int* primer, int& primer_num)
  2. {
  3. primer_num = 0;
  4. int sqrt_i, i, j;
  5. for (i = 2; i <= n; i++)
  6. {
  7. sqrt_i = (int)sqrt(i);
  8. for (j = 2; j <= sqrt_i; j++)
  9. if (i%j == 0)
  10. break;
  11. if (j > sqrt_i)
  12. primer[primer_num++] = i;
  13. }
  14. }

 2.筛选法:这种方法主要用于打素数表,如求出n之内的所有素数,其思路是从1开始遇到一个素数就标记一下,并去掉n之内的大于它的所有倍数,直循环到n:

此方法也有局限性,数据量中等时才不会超时,数据量过大时也会超时,而且只能用素数打表,不能对单个数进行判定!

  1. void PrimeNumber(int n, int* primer, int& primer_num)
  2. {
  3. if (n < 2)
  4. {
  5. primer_num = 0;
  6. return;
  7. }
  8. primer[0] = 2;
  9. primer_num = 1;
  10. for (int i = 1; i < n / 2 + 1; i++)
  11. primer[i] = true;
  12. for (int i = 1; i < n / 2 + 1; i++)
  13. {
  14. if (primer[i] && (2 * i + 1) <= n)
  15. {
  16. primer[primer_num++] = 2 * i + 1;
  17. for (int j = 3 * i + 1; j < n / 2 + 1; j = j + 2 * i + 1)
  18. primer[j] = false;
  19. }
  20. }
  21. }

3.《离散数学》上的一个定理

  1. bool IsPrimerNum(int n, int* primer, int&primer_num)
  2. {
  3. int sqrt_i= (int)sqrt(n);
  4. for (int i = 0; primer[i] <= sqrt_i&&primer_num; i++)
  5. {
  6. if (n%primer[i] == 0)
  7. return 0;
  8. }
  9. return 1;
  10. }
  11. void PrimeNumber(int n, int* primer, int& primer_num)
  12. {
  13. primer_num = 0;
  14. for (int i = 2; i <= n; i++)
  15. if (IsPrimerNum(i, primer, primer_num))
  16. primer[primer_num++] = i;
  17. }

参考:http://blog.csdn.net/liukehua123/article/details/5482854
参考:大神http://blog.csdn.net/arvonzhang/article/details/8564836

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注