素数について

[gray]

以下にchar型の配列に一文字ずつ数字を入れたデータ構造を作りました

コード:

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

#define NUMDIGITS 158
typedef struct{
	char val[NUMDIGITS];
}subnt;

subnt vi_assign(long long);
subnt vi_zero(void);
void vi_print(subnt);
int vi_keta(subnt);
subnt vi_add(subnt, subnt);
subnt vi_sub(subnt, subnt);
subnt vi_mul(subnt, subnt);
subnt vi_div(subnt, subnt);
int vi_compare(subnt , subnt);

subnt vi_mod(subnt, subnt);
int main(void){
	subnt   g=vi_assign(2), f=vi_assign(1000000000000037LL), p=vi_zero(), o=vi_assign(1), l=vi_zero(), i=vi_assign(2), w=vi_assign(1), j=vi_assign(9999999999999937LL);
	int d, c;
	for(d=0;d<4;d++){
		l=vi_zero();
		p=vi_zero();
		g=vi_assign(2);
		f=vi_add(f, w);

	while(1){
		
			l=vi_add(l, o);
		
			p=vi_mod(g, f);
			if(p.val[0]==2 && vi_compare(l, f)==3){
				vi_print(f);
				break;
			}else if(p.val[0] !=2 && vi_compare(l, f)==3)break;

		g=vi_mul(p, i);
	}
		
	}
	for(c=0;c<4;c++){
		l=vi_zero();
		p=vi_zero();
		g=vi_assign(2);
		j=vi_add(j, w);

	while(1){
		
			l=vi_add(l, o);
		
			p=vi_mod(g, j);
			if(p.val[0]==2 && vi_compare(l, j)==3){
				vi_print(j);
				break;
			}else if(p.val[0] !=2 && vi_compare(l, j)==3)break;

		g=vi_mul(p, i);
	}
		
	}
	return 0;
}


subnt vi_zero(void){
	int i;
	subnt tmp;

	for(i=0;i<NUMDIGITS;i++){
		tmp.val[i]=0;
	}
		return tmp;
}

subnt vi_assign(long long num){
 
	subnt tmp=vi_zero();
	int i;
	long long k, p;
    for(i=0;num>0;i++){
		k=num/10;
		p=num-10*k;
        tmp.val[i]=(char)p;
        num=num/10;
    }
    return tmp;
}

void vi_print(subnt var){
    int i=vi_keta(var)-1;
    
	if(i<0){
		i=0;
	}

    for(i=vi_keta(var)-1;i>-1;i--){
        printf("%01d",var.val[i]);
    }
    printf("\n");
}

int vi_keta(subnt var){
	int i=NUMDIGITS-1;
	while(var.val[i]==0){
		i--;
		if(i==0)break;
	}
	return i+1;
}


subnt vi_add(subnt a,subnt b){
    int i,k;
    if(vi_keta(a)>=vi_keta(b))k=vi_keta(a);
    else k=vi_keta(b);
    for(i=0;i<k;i++){
        a.val[i]=a.val[i]+b.val[i];
        
        if(a.val[i]>=10){
            a.val[i]=a.val[i]-10;
            a.val[i+1]++;
        }
    }
    return a;
}
 

subnt vi_sub(subnt a, subnt b){
	int i, k;
	char d;
	if(vi_keta(a)>=vi_keta(b)){
		k=vi_keta(a);
	}else{
		k=vi_keta(b);
	}
	for(i=0;i<k;i++){
        if(vi_compare(a, b)==0){
			d=b.val[i];
			b.val[i]=a.val[i];
			a.val[i]=d;
		}
		if(a.val[i]<b.val[i]){
			a.val[i]=10+a.val[i]-b.val[i];
			a.val[i+1]=a.val[i+1]-1;			
		}else{
		
		a.val[i]=a.val[i]-b.val[i];
		}			
		if(a.val[i]>=10){
			a.val[i]=a.val[i]-10;
			a.val[i+1]++;
		}
	}
	return a;	
}



subnt vi_mul(subnt a,subnt b){
 
    subnt v=vi_zero(),seki=vi_zero();
 
    int i,j,ak=vi_keta(a),bk=vi_keta(b);
 
    for(i=0;i<bk;i++,v=vi_zero()){
 
        for(j=0;j<ak;j++){
            v.val[j+i]=a.val[j]*b.val[i]+v.val[j+i];
 
            if(v.val[j+i]>=10){
                v.val[j+i+1]=v.val[j+i]/10;
                v.val[j+i]=v.val[j+i]%10;
            }
        }
        seki=vi_add(v,seki);
    }
    return seki;
}

subnt vi_div(subnt a, subnt b){
	subnt v=vi_zero(), i=vi_assign(1),k=vi_assign(1);
 
    int  j;
	 while(1){
		 j=vi_compare(a, b);
		 if(j==0){
			 break;
		 }else if(j==2 ||j==3){
			 v=vi_sub(a, b);
			 k=vi_add(k, i);
			 a=v;
	 }
	
	 }
	 k=vi_sub(k, i);
	return k;
}

int vi_compare(subnt a, subnt b){
	int ak=vi_keta(a), bk=vi_keta(b), j=0, l=ak-1;
	if(ak>bk){
	j=2;
	
	}else if(ak<bk){
		j=0;
	
	}else if(ak==bk){
		while(1){
			
		if(a.val[l]>b.val[l]){
			j=2;
			break;
		}else if(a.val[l]==b.val[l]){
			l--;
		}else if(a.val[l]<b.val[l]){
			j=0;
			break;
		}
	     if(l==0){
			 if(a.val[0]==b.val[0]){
				j=3;
				break;
			}else if(a.val[0]<b.val[0]){
				j=0;
				break;
			 }else if(a.val[0]>b.val[0]){
				j=2;
				break;
			}
		 }
		}

	
	
	}
	return j;
}


subnt vi_mod(subnt a, subnt b){
	subnt c, d, e;

	c=vi_div(a, b);
	d=vi_mul(b, c);
	e=vi_sub(a, d);

	return e;
}

今このデータ構造を使って16桁の素数をみつけようとしています
そのため、素数の判定方法としてフェルマーの小定理を使用しました
しかしあまりに大きい数のため実行時間が長くなってしまいました
どうすれば実行時間を短く出来るでしょうか？

[non]

プログラムは見ていませんが、このページに参考になることが書かれてます。
この方法は試されていますか？
http://www2.cc.niigata-u.ac.jp/~takeuch ... power.html

[みけCAT]

1文字ずつではなく、例えばintに9桁ずつ入れるというようにすれば、定数倍が改善されるかもしれません。
あとは自分もわかっていませんが、乗算にFFTを使う、とかでしょうか？