现在的位置: 首页 > 综合 > 正文

利用素数表快速寻找 n 以内的所有素数

2018年12月12日 ⁄ 综合 ⁄ 共 2542字 ⁄ 字号 小 中 大 ⁄ 评论关闭

http://blog.csdn.net/wxyztuv/article/details/7965556

三个函数，find_prime() 是利用素数表的方法，寻找素数的，find_prime_stupid()是利用另一种传统方法寻找素数的，test_func()用于测试两个函数的速度

测试数据分别是　1000,5000,10000,50000,100000,500000,1000000,2000000,5000000　以内的素数。

[cpp] view
plaincopy

  1. #include <stdio.h>  
  2. #include <stdlib.h>  
  3. #include <windows.h>  
  4. #include <math.h>  
  5. #include <time.h>  
  6.   
  7. #define SIZE 10000000  
  8.   
  9. void find_prime(int n);  
  10. void find_prime_stupid(int n);  
  11. int test_func(void);  
  12.   
  13. // 建立一个素数表  
  14. int prime[SIZE] = {0};  
  15. int prime_index = 0;        // 素数表索引  
  16.   
  17.   
  18. int main(int argc,char **argv)  
  19. {  
  20.     test_func();  
  21.     return 0;  
  22. }  
  23.   
  24.   
  25. // 速度测试函数  
  26. int test_func(void)  
  27. {  
  28.     time_t start_time,end_time;  
  29.     int test_data[] = {1000,5000,10000,50000,100000,500000,1000000,2000000,5000000,0};  
  30.     int i_testdata = 0;  
  31.       
  32.     printf("\n\nstart testing...\n\n");  
  33.   
  34.     // 测试 find_prime() 函数  
  35.     printf("find_prime():\n");  
  36.     while(test_data[i_testdata])  
  37.     {  
  38.         printf("%d\t\t",test_data[i_testdata]);  
  39.         time(&start_time);  
  40.   
  41.         find_prime(test_data[i_testdata]);  
  42.   
  43.         time(&end_time);  
  44.         printf("%ds\n",end_time - start_time);  
  45.         ++i_testdata;  
  46.   
  47.     }  
  48.   
  49.     // 测试 find_prime_stupid() 函数  
  50.     printf("\n\n");  
  51.     i_testdata = 0;  
  52.     printf("find_prime_stupid():\n");  
  53.     while(test_data[i_testdata])  
  54.     {  
  55.         printf("%d\t\t",test_data[i_testdata]);  
  56.         time(&start_time);  
  57.   
  58.         find_prime_stupid(test_data[i_testdata]);  
  59.   
  60.         time(&end_time);  
  61.         printf("%ds\n",end_time - start_time);  
  62.         ++i_testdata;  
  63.     }  
  64.   
  65.   
  66.     return 0;  
  67. }  
  68.           
  69.   
  70.   
  71. // 若n是合数，则n必有小于或等于n的正平方根(根号n)的一个素因子  
  72. // 遍历当前素数表，如果当前索引的值不为0，  
  73. // 并且值不超过了n的正平方根，并且当前值不能整除i，  
  74. // 则检查素数表的下一个素数  
  75. // 当素数表循环检查停止，检查停止处的索引值，  
  76. // 如果值为0，或者值不能整除i，  
  77. // 则将i加入素数表  
  78.   
  79.   
  80. void find_prime(int n)  
  81. {  
  82.     for(int i = 2; i <= n; ++i)  
  83.     {  
  84.         int j = 0;  
  85.           
  86.         while(prime[j] && i % prime[j] != 0 && prime[j] <= sqrt(i))  
  87.         {  
  88.             ++j;  
  89.         }  
  90.           
  91.         if(!prime[j] || i % prime[j] != 0)  
  92.         {  
  93.             prime[prime_index++] = i;  
  94.            // printf("%d  ",i);  
  95.         }  
  96.     }  
  97. }  
  98.       
  99.   
  100. void find_prime_stupid(int n)  
  101. {  
  102.     int is_prime = 1;  
  103.     for(int i = 2; i <= n; ++i)  
  104.     {  
  105.         for(int j = 2; j <= sqrt(i); ++j)  
  106.         {  
  107.             if(i % j == 0)  
  108.             {  
  109.                 is_prime = 0;  
  110.             }  
  111.         }  
  112.           
  113.         if(is_prime)  
  114.         {  
  115.           //  printf("%d  ",i);  
  116.         }  
  117.         else  
  118.         {  
  119.             is_prime = 1;  
  120.         }  
  121.     }  
  122. }  

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞