分享一个筛法求素数的代码

1121098405

我在虚拟机上运行找一亿以内的素数只用了0.6s左右

1. #include <stdlib.h>
   
2. #include <time.h>
   
3. #include <stdio.h>
   
4. 
   
5. unsigned int *get_primes(unsigned int size)
   
6. {
   
7.     unsigned int i, j, limit, *primes, max = size * 2 + 1;
   
8. 
   
9.     primes = (unsigned int *)malloc(sizeof(*primes) * size);
   
10. 
    
11.     for (i = 0; i < size; i++)
    
12.     {
    
13.         primes[i] = i * 2 + 3;
    
14.     }
    
15. 
    
16.     for (i = 0; i < size; i++)
    
17.     {
    
18.         if (primes[i])
    
19.         {
    
20.             if (primes[i] > (limit = max / primes[i]))
    
21.                 break;
    
22. 
    
23.             for (j = primes[i]; j <= limit; j += 2)
    
24.             {
    
25.                 primes[(primes[i] * j - 3) / 2] = 0;
    
26.             }
    
27.         }
    
28.     }
    
29. 
    
30.     return primes;
    
31. }
    
32. 
    
33. void prime(unsigned int max)
    
34. {
    
35.     unsigned int *primes, count = 1, i, size = max / 2;
    
36.     clock_t start, stop;
    
37.     int duration;
    
38. 
    
39.     start = clock();
    
40.     primes = get_primes(size);
    
41.     stop = clock();
    
42.     duration = (int)((double)(stop - start) / CLOCKS_PER_SEC * 1000);
    
43. 
    
44.     for (i = 0; i < size; i++)
    
45.     {
    
46.         if (primes[i])
    
47.         {
    
48.             count++;
    
49.         }
    
50.     }
    
51. 
    
52.     free(primes);
    
53. 
    
54.     printf("在 %dms 内找到%u个质数\n", duration, count);
    
55. }

复制代码