求10的10次方以内的素数，怎么能在几小时内算出来结果？

zliming

有人算出来了没有？
我算了4小时出来
2.xxxx^10
不过IO应该占了大部分时间。不IO输出又不知道进度...
这次算完了把IO去掉，只最后一次输出结果

看错时间，近两小时了,4.xxxx ^10

[ 本帖最后由 zliming 于 2009-4-21 17:20 编辑 ]

prolj

把code帖出来吧，有时间我跑一下。

zliming

#include <stdlib.h>
#include <memory.h>
#include <time.h>
#include <stdio.h>
#include <math.h>
typedef unsigned long long uint;
const uint MAX_NUM = 10000000000;

static int* ret_bit = NULL;

void init_ret_bit()
{
    uint size = MAX_NUM / 8 / 2 + 10;
    ret_bit = (int*)malloc(size);
    memset(ret_bit, 0xff, size);
}
void free_ret_bit()
{
    free(ret_bit);
    ret_bit = NULL;
}
inline bool get_bit(uint i)
{
    i = i / 2 - 1;
    return ret_bit[i >> 5] & (1 << (i & 31));
}
inline void clear_bit(uint i)
{
    i = i / 2 - 1;
    ret_bit[i >> 5] &= ~(1 << (i & 31));
}
int main(int, char*[])
{
    time_t start = time(NULL);
    init_ret_bit();
#if 0
    for(uint i = 3; i <= sqrt((double)MAX_NUM); i+=2)
    {
        if(get_bit(i))
        {
            for(uint j = i + 2; j < MAX_NUM; j+=2)
            {
                if(get_bit(j) && (j % i == 0))
                    clear_bit(j);
            }
        }
    }
#else
    for(uint i = 3; i <= sqrt((double)MAX_NUM);  i+=2)
    {
        if(get_bit(i))
        {
            uint i2 = i + i;
            for(uint j = i2 + i; j < MAX_NUM; j += i2)
                clear_bit(j);
        }
    }
#endif
    //for(uint i = 3; i < MAX_NUM; i+=2)
    //    if(get_bit(i))
    //        printf("%u\n", i);
    //只输出个数，太多东西了
    int all_count = 0;
    for(uint i = 3; i < MAX_NUM; i+= 2)
        if(get_bit(i))
            all_count++;
    printf("count = %d, time = %d", all_count, time(NULL) - start);

    free_ret_bit();
    system("pause");
    return 0;
}

下面的实现法快很多了，网友kaikai帮助优化

[[i] 本帖最后由 zliming 于 2009-4-21 22:46 编辑 [/i]]

zliming

count = 455052510, time = 1878请按任意键继续. . .
半小时多，不知道结果个数对不对

prolj

kaikai出面了？浙大博士？

zliming

可能你认错人了，这个kaikai同济搞游戏的

koolcoy

修改了一下代码
1. 在改成了windows下vc 2005可以编译运行的
2. 参照zliming， 位图使用int*代替char*

说明一下， 位图的存取必须用宏或者inline（编译器优化成inline的也可以）， 否则函数调用的开销非常大。

运行结果:
Total: 455052511, Time: 904

1. 
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. #include <time.h>
   
5. #include <string.h>
   
6. 
   
7. #define CLEAR(map, bit) (map)[(bit) / 32] &= ~(1 << (bit % 32))
   
8. #define GET(map, bit) ((map)[(bit) / 32] & (1 << (bit % 32)))
   
9. 
   
10. const static long long SQUARE_ROOT = 100000;
    
11. const static long long BOUND = SQUARE_ROOT * SQUARE_ROOT;
    
12. 
    
13. int main() {
    
14.         unsigned long long i = 0;
    
15.                 int start = time(NULL);
    
16.         int* map = (int*)malloc(BOUND / 8 + 1);
    
17.         if (map == 0) {
    
18.                 printf("Oh no\n");
    
19.                 exit(1);
    
20.         }
    
21.         memset(map, 0xff, BOUND / 8 + 1);
    
22. 
    
23.         CLEAR(map, 1);
    
24.         for (i = 1; i < SQUARE_ROOT; i++) {
    
25.                 if (!GET(map, i)) continue;
    
26.                 printf("%lld\n", i);
    
27.                 long long j = i * 2;
    
28.                 for (; j < BOUND; j += i) {
    
29.                         CLEAR(map, j);
    
30.                 }
    
31.         }
    
32.                 long long total = 0;
    
33.         for (i = 1; i < BOUND; i++) {
    
34.                 if (GET(map, i)) {
    
35.                         total++;
    
36.                 }
    
37.         }
    
38.                 printf("Total: %lld, Time: %d\n", total, time(NULL) - start);
    
39.                 system("pause");
    
40. }
    

复制代码

[ 本帖最后由 koolcoy 于 2009-4-22 10:51 编辑 ]

koolcoy

原帖由 zliming 于 2009-4-21 23:23 发表
count = 455052510, time = 1878请按任意键继续. . .
半小时多，不知道结果个数对不对

我比你的结果多一个~~~， 看来是正确的

ps: 我感觉你漏了一个数， 不信你把上限改成100， 你多半把97漏了~

[ 本帖最后由 koolcoy 于 2009-4-22 10:54 编辑 ]

zliming

我漏了一个2，这个我清楚的，loop从3开始的

zliming

偶数不是质数
我 ret_bit 里直接是从3开始的奇数，不过内存也要700+M