鐃夙わ申鐃緒申鐃緒け鐃叔随申鐃緒申直鐃緒申鐃緒申鐃緒申鐃�

鐃熟てなブッワ申鐃殉￥申鐃緒申 - mohno鐃塾ブッワ申鐃殉￥申鐃緒申
鐃緒申Core i7 鐃緒申 iMac 鐃叔￥申10鐃緒申鐃緒申鐃熟囲を検削申鐃緒申鐃緒申里鐃�1鐃竣ワ申鐃緒申鐃緒申300鐃緒申鐃緒申鐃緒申廣鐃緒申戮鐃緒申辰討鐃緒申函鐃緒申鐃緒申鐃緒申鐃夙ワ申鐃銃ネワ申鐃塾ふるい鐃叔￥申鐃緒申鐃縦誌申竜鐃緒申鐃緒申任鐃�10鐃緒申鐃淑わ申2分鐃緒申Core i7 920鐃祝￥申鐃緒申亮蠍居申任鐃�20鐃獣￥申Core 2 Duo E6850鐃祝わ申鐃獣わ申鐃緒申鐃緒申鐃緒申鼻鐃�

10鐃獣わ申鐃准ってわ申鐃殉っわ申鐃塾で￥申

鐃緒申鐃祝ワ申鐃暑ゴ鐃所ズ鐃緒申任鐃緒申襪�鐃緒申鐃緒申鐃緒申鐃緒申鐃緒申鐃緒申鐃緒申鐃獣てみわ申鐃緒申未鐃緒申鐃緒申鐃緒申鐃緒申鐃�

  1. 鐃殉わ申 p < 256 鐃淑常申鐃緒申鐃緒申鐃叔随申鐃叔ワ申鐃緒申肇鐃緒申謄優鐃緒申里佞襪わ申砲鐃緒申鐃�
  2. 鐃緒申鐃緒申Miller-Rabin鐃叔随申判鐃緒申法鐃緒申適鐃術わ申鐃緒申

鐃緒申鐃緒申蓮峺帖鐃緒申鐃�64bit鐃緒申鐃緒申鐃緒申鐃叔随申鐃緒申鐃宿わ申鐃緒申鐃竣わ申判鐃所す鐃緒申里砲鐃�(鐃叔随申表鐃緒申鐃緒申鐃緒申鐃緒申箸鐃緒申鐃緒申鐃緒申)鐃駿ワ申鐃夙に近い鐃緒申法鐃淑のわ申鐃緒申鐃緒申鐃緒申任鐃春わ申鐃熟囲わ申鐃緒申鐃緒申鐃緒申鐃叔随申鐃緒申鐃緒申鐃銃上げ鐃緒申廚箸鐃緒申鐃緒申鐃緒申鐃祝は実わ申適鐃緒申鐃銃わ申鐃淑わ申鐃緒申鐃緒申任鐃春わ申鐃熟囲」わ申鐃緒申鐃銃ワ申鐃所ー鐃緒申鐃緒申屬鐃緒申鐃塾でわ申鐃緒申弌鐃緒申鐃緒申鐃緒申鐃縦常申椒鐃緒申鐃夙ワ申鐃銃ネワ申鐃塾ふるい鐃薯かわ申鐃緒申鐃緒申鐃縦っわ申鐃緒申鐃薯あわ申鐃緒申鐃緒申鐃緒申速鐃緒申鐃塾わ申鐃緒申

鐃殉わ申鐃緒申32bit鐃緒申鐃叔随申表鐃薯あらか鐃緒申鐃緒申鐃獣てわ申鐃緒申鐃緒申

mksieve32.c

/*
 * $Id: mksieve32.c,v 0.1 2010/07/27 15:21:58 dankogai Exp dankogai $
 */
#include <stdlib.h>
#include <stdio.h>
#include <limits.h>

#include <stdint.h>
typedef uint32_t U32;
typedef uint64_t U64;

#include "bitmap.c"

int main(void) {
    bitmap *b = bitmap_new((U64)INT_MAX+1, NULL);
    bitmap_fill(b, 1);
    bitmap_set( b, 0, 0); /* 1 is not prime */
    U64 p, i;
    for (p = 3; p < USHRT_MAX ;){
        printf("sieving %llu\r", p);
        fflush(stdout);
        for ( i = p + p ; i <=  UINT_MAX ; i += p ) {
            if ((i & 1) == 0) continue; /* skip even */
            bitmap_set( b, i>>1, 0 );
        }
        for(p += 2; !bitmap_get(b, p>>1); p += 2); /* seek next prime */
    }
    char filename[]  = "sieve32.bm";
    printf("saving %s\n", filename);
    bitmap_save(b, filename);
    return 0;
}

鐃緒申鐃曙自鐃塾￥申(鐃盾う鐃緒申鐃緒申鐃緒申鐃緒申鐃緒申鐃駿わ申砲覆鐃�?)Core i7鐃緒申iMac鐃緒申鐃緒申30鐃獣ほどわ申鐃緒申鐃緒申鐃緒申鐃緒申覆鐃緒申鐃緒申覆鐃緒申鐃�bitmap.c鐃緒申鐃縦ワ申鐃緒申董鐃�bitmap_fill()鐃緒申bitmap_save()鐃緒申鐃宿加わ申鐃緒申鐃緒申鐃緒申鐃緒申蕕�鐃緒申鐃薯するか鐃熟種申鐃緒申鐃叔わ申鐃緒申鐃緒申鐃緒申鐃緒申鐃淑みわ申bitmap_load()鐃緒申鐃淑わ申鐃塾は￥申bitmap_new()鐃祝わ申鐃塾居申能鐃緒申鐃緒申鐃叔わ申存鐃淳わ申鐃暑か鐃初。

primes.c

鐃緒申鐃夙はわ申鐃緒申32bit鐃叔随申表鐃緒申鐃緒申鐃術わ申鐃緒申亳鐃緒申鐃重�鐃祝わ申64bit鐃緒申鐃緒申鐃緒申鐃叔随申鐃緒申鐃緒申鐃銃随申鐃緒申鐃遵げ鐃暑こ鐃夙わ申鐃叔わ申鐃緒申錣縁申鐃緒申鐃緒申鐃緒申鐃緒申鐃緒申鐃緒申戮鐃緒申鐃緒申鐃緒申鐃緒申砲佞襪わ申鬚�わ申鐃緒申里任呂覆鐃緒申鐃緒申鐃緒申鐃緒申泙鐃緒申楼六鐃緒申蠅件申鐃緒申楼呂里澆砲鐃緒申鐃緒申襦ｏ申鐃緒申鐃緒申鐃緒申鐃塾縁申佞鐃緒申鐃出￥申mksieve32.c鐃夙わ申辰討襪鰹申箸鐃緒申腓件申鐃緒申僂鐃緒申覆鐃緒申鐃�

/*
 * $Id: primes.c,v 0.2 2010/07/27 15:35:59 dankogai Exp dankogai $
 */
#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#include <errno.h>
#include <math.h>

#include <stdint.h>
typedef uint32_t U32;
typedef uint64_t U64;

#include "bitmap.c"

#define SIEVEFILE "sieve32.bm"

int main(int argc, char **argv) {
    bitmap *sieve = bitmap_new(0, SIEVEFILE);
    if (!sieve){
        perror(SIEVEFILE);
        exit(errno);
    }
    U64 start = argc > 1 ? atoll(argv[1]) : 0;
    U64 size  = argc > 2 ? atoll(argv[2]) : 1000*1000*1000;
    bitmap *b = bitmap_new(size >> 1, NULL);
    bitmap_fill(b, 1);
    if (start == 0) bitmap_set(b, 0, 0);
    U64 pmax = (U64)sqrtl(start+size);
#ifdef VERBOSE
    printf("pmax = %llu\n", pmax);
#endif
    U64 p, i;
    for (p = 3; p < pmax;){
#ifdef VERBOSE
        printf("sieving %llu\r", p);
        fflush(stdout);
#endif
        for ( i = p + p - (start % p) ; i <= size ; i += p ) {
            if ((i & 1) == 0) continue; /* skip even */
            bitmap_set( b, i>>1, 0 );
        }
        for(p += 2; !bitmap_get(sieve, p>>1); p += 2); /* seek next prime */
    }

    char filename[256];
    snprintf(filename, 256, "%llu~%llu.bm", start, start+size);
#ifdef VERBOSE
    printf("saving %s\n", filename);
#endif
    bitmap_save(b, filename);
    return 0;
}

鐃緒申鐃緒申鐃夙わ申鐃夙￥申10鐃緒申鐃淑駕申鐃叔わ申鐃緒申鐃�10鐃獣種申鐃緒申楼鐃�10鐃緒申鐃塾醐申鐃緒申鐃緒申鐃緒申鐃緒申襦�999,999,999,000,000,000~1,000,000,000,000,000,000鐃緒申鐃緒申鐃淑わ申鐃�10鐃緒申鐃緒申傍鐃緒申10鐃緒申鐃叔わ申鐃緒申15鐃獣ほどでわ申鐃獣わ申鐃緒申10鐃緒申鐃叔わ申鐃緒申鐃緒申辰鐃緒申鐃緒申鷁修鐃緒申覆鐃緒申箸鐃�1鐃緒申鐃緒申鐃駿で緒申鐃緒申鐃夙わ申鐃緒申鐃緒申鐃夙になる。必鐃竣なデワ申鐃緒申鐃緒申鐃緒申鐃縮わ申61M鐃塾逸申鐃緒申鐃旬なのわ申610G鐃夙わ申鐃獣わ申鐃夙わ申鐃緒申鐃緒申鐃緒申

cover
鐃縮子ワ申鐃緒申團紂種申鐃�
鐃緒申鐃緒申 鐃祝種申
10鐃緒申鐃殉でわ申鐃叔随申鐃塾リス鐃夙わ申鐃獣てみまわ申鐃藷か￥申 - 鐃緒申鐃峻の眼：ITpro
鐃緒申鐃峻わ申鐃叔緒申縫廛鐃緒申鐃緒申鐃緒申鐃書いわ申鐃塾は￥申鐃重居申店鐃緒申店頭鐃祝わ申鐃獣わ申8鐃俊ット居申鐃緒申鐃緒申鐃緒申鐃緒申鐃緒申鐃塾マワ申鐃緒申鐃緒申任呂箸討發鰹申鐃淑とわ申鐃緒申鐃殉でわ申鐃緒申鐃淑わ申鐃獣わ申鐃緒申鐃叔わ申鐃緒申鐃緒申鐃縦刻申鐃緒申鐃緒申鐃緒申董鐃緒申泙鐃緒申鐃緒申鐃緒申鵐犬鐃緒申討澆鐃緒申鐃緒申隼廚鐃緒申鐃�

鐃緒申鐃緒申鐃緒申蓮鐃�鐃緒申鐃殉￥申鐃緒申鐃緒申鐃緒申鐃緒申鐃竣にわ申鐃緒申鐃獣わ申鐃出場し鐃緒申Shor鐃塾ワ申鐃暑ゴ鐃所ズ鐃緒申鐃緒申鐃緒申鐃緒申鐃緒申鐃緒申婿劵鐃緒申鐃峻ュー鐃緒申鐃緒申鐃出場し鐃銃￥申RSA鐃祝使わ申鐃銃わ申鐃緒申茲�鐃緒申鐃順き鐃淑随申鐃緒申鐃叔随申判鐃緒申鐃緒申屬能鐃緒申鐃緒申茲�鐃祝なわ申鐃緒申鐃緒申鐃緒申襪�鐃盾し鐃緒申覆鐃緒申鐃緒申鐃緒申鐃緒申鐃緒申鐃緒申鐃緒申鐃緒申鐃緒申鐃銃も、鐃緒申鐃緒申肇鐃緒申謄優鐃緒申里佞襪わ申呂鐃緒申泙鐃緒申泙雰鐃緒申濃箸鐃緒申続鐃緒申鐃緒申鐃緒申鐃緒申鐃緒申鐃緒申發件申鐃緒申鐃緒申董鐃緒申鐃緒申鐃緒申鐃祝器申鐃盾。

Dan the Prime Counter

bitmap.c

/*
 * $Id: bitmap.c,v 0.2 2010/07/27 15:27:02 dankogai Exp dankogai $
 */
#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <fcntl.h>
#include <sys/stat.h>
#include <sys/mman.h>

typedef struct {
    int    fd;
    size_t size;
    char  *map;
} bitmap;

bitmap *bitmap_free(bitmap *b){
    if (b){
        if (b->map) {
            if (b->fd){
                munmap(b->map, b->size);
                close(b->fd);
            }else{
                free(b->map);
            }
        }
        free(b);
    }
    return (bitmap *)NULL;
}

bitmap *bitmap_new(size_t size, const char *filename){
    bitmap *b = (bitmap *)malloc(sizeof(bitmap));
    struct stat st;
    if (!b) return (bitmap *)NULL;
    if (filename){
        b->fd = open(filename, 
                     size ? O_RDWR|O_CREAT : O_RDONLY, 
                     size ? (mode_t)0644   : (mode_t)0444);
        if (b->fd == -1) {
            perror(filename);
            return bitmap_free(b);
        }
        if (size){
            if (ftruncate(b->fd, size >> 3) == -1){
                perror(filename);
                return bitmap_free(b);
            }
            b->map = (char *)mmap(0, size >> 3, PROT_READ|PROT_WRITE,
                                  MAP_SHARED, b->fd, 0);

        }
        else{
            fstat(b->fd, &st);
            size = st.st_size << 3;
            b->map = (char *)mmap(0, size >> 3, PROT_READ, 
                                  MAP_PRIVATE, b->fd, 0);
        }
        if (b->map == MAP_FAILED) return bitmap_free(b);
    }
    else{
        if (!size) return (bitmap *)NULL;
        b->map = (char *)malloc(size >> 3);
        if (!b->map) return bitmap_free(b);
        b->fd = 0;
    }
    b->size = size;
    return b;
}

int bitmap_save(bitmap *b, const char *filename){
    int ok = 0, fd = open(filename, O_RDWR|O_CREAT|O_TRUNC, (mode_t)0644);
    if (fd != -1){
        if (write(fd, b->map, (b->size >> 3)) != -1) ok = 1;
    }
    if (!ok) perror(filename);
    close(fd);
    return ok;
}

void bitmap_fill(bitmap *b, int val){
    size_t i;
    for (i = 0; i < (b->size >> 3); i++) b->map[i] = val ? 0xff : 0;
}

static const int bits[] = { 1, 2, 4, 8, 16, 32, 64, 128 };

inline int bitmap_set(bitmap *b, size_t where, int val){
    if (val) b->map[where >> 3] |=  bits[where & 7];
    else b->map[where >> 3] &= ~bits[where & 7];
    return val;
}

inline int bitmap_get(bitmap *b, size_t where){
    return !!(b->map[where >> 3] & bits[where & 7]);
}

#ifdef TEST
#include <errno.h>
int main (int argc, char **argv){
    bitmap *b = bitmap_new(4096, (argc > 1 ? argv[1] : NULL));
    if (!b) return errno;
    bitmap_set(b, 0, 1);
    printf("%d\n", bitmap_get(b, 0));
    bitmap_free(b);
    return 0;
}
#endif