bigint、素数判定

というものがあることを知った。cpanからインストールして

use bigint;

を書くと1023乗より大きい数を計算できた。

2のベキ乗を計算させると

1.28421286658896e+207

という表示ではなく、全桁表示する。

たとえば２の1247乗

2423285551989543969259886147306320615721694717012975552426444448158985017722789267546553034738712987127346362442309271495645764807314487385596126924659433020959638410571315406303196994043324038030803068668509323897700215957022383545283810557899591580902307500436706661372076856211818662627186819885605667216486349283517459646495626188985295134800963771933733229691796170211328

ちなみにこんなのもある。

なんでこれで判定できるのかさっぱりわからない。

perl -le 'print "PRIME" if (1 x shift) !~ /^(11+)\1+$/' 19

http://www.drdobbs.com/web-development/tpj-one-liners/184416234




「フェルマー小定理」方式C言語版

判定できる最大の素数は 16381である。

#include <stdio.h>
#include <math.h>

long double gojo(long double a, long double b);

int main(int argc, char *argv[]){
long double d;
long double  a, m, p, x;
int count, max;

count = 0;
a = 2;

if(argc > 1) {
    max = atoi(argv[1]);
}else{
    printf("please specify max number.\n");
    return 1;
}

printf("start\n");

for(p=3;p<max;p++){
    x = gojo(p, 2L);
    if(x == 1){
        d = powl(a, p-1);
        m = fmodl(d, p);
        if(m == 1){
            printf ("%.1Lf is PRIME\n", p);
            count++;
        }
    }
}

printf("end\n");
printf("count:%d\n", count);
}

long double gojo(long double a, long double b){
    long double c;

    while(b>0) {
        c = fmodl(a, b);
        a = b;
        b = c;
    }
    return a;
}