426,012 Members | 988 Online
Need help? Post your question and get tips & solutions from a community of 426,012 IT Pros & Developers. It's quick & easy.

# Faster algorithm for prim numbers in C...???

 P: n/a Dear, I weated a simple program, he is compiled with gcc, and generates prim numbers, with fastes method that I find.He is based on divide with generated prim numbers... At end he gives time report on format: dd:hh:mi:sec... Precompile as gcc prim.c -o prim, and use him as "prim upper_bound",as example: "prim 1000".If anybody have some idea how to make algorithm fastes write to me...!! //---------------------------------------------------------- #include #include #include void transform(char*, int); struct lst{ long int value; struct lst* next; }; int main(int argc, char* argv[]){ long int i,j,k, time_begin, time_end, razlika_vremena; char trans_value[20]; struct lst *prvi, *tekuci_prvi, *tekuci_drugi, *zadnji; prvi=(struct lst*)malloc(sizeof(struct lst)); prvi->next=(struct lst*)malloc(sizeof(struct lst)); prvi->value=1; prvi->next->value=2; tekuci_prvi=prvi->next; zadnji=prvi->next; zadnji->next=(struct lst*)NULL; k=atoi(argv[1]); tekuci_drugi=prvi; time(&time_begin); for(i=1;inext){ if((i%(tekuci_drugi->value)==0) && tekuci_drugi->value!=1){ if(i==1){ goto exit; } i++; goto exit; } tekuci_drugi=tekuci_drugi->next; } tekuci_prvi->next=(struct lst*)malloc(sizeof(struct lst)); tekuci_prvi=tekuci_prvi->next; tekuci_prvi->value=i; tekuci_prvi->next=(struct lst*)NULL; /*printf("%ld\n",i);*/ } tekuci_prvi=prvi; while(tekuci_prvi->next){ printf("%d\n", tekuci_prvi->value); tekuci_prvi=tekuci_prvi->next; } time(&time_end); razlika_vremena=time_end-time_begin; transform(&trans_value, razlika_vremena); printf("\nGeneriranje i stampanje do %d broja je trajalo:%s", k, trans_value); exit(0); } void transform(char* t, int time){ int days, hours, minuts, seconds, i, timi; char dd[5],hh[3],mi[3],sec[3]; timi=time; days=time/(24*3600); i=time%(24*3600); time=time/(24*3600)+i; hours=(time/3600); i=time%3600; time=time/3600+i; minuts=time/60; time=time/60; time=time%60; seconds=timi-days*3600*24-hours*3600-minuts*60; if(days<10){ sprintf(dd,"0%d",days); }else{ sprintf(dd,"%d",days); } if(hours<10){ sprintf(hh,"0%d",hours); }else{ sprintf(hh,"%d",hours); } if(minuts<10){ sprintf(mi,"0%d",minuts); }else{ sprintf(mi,"%d",minuts); } if(seconds<10){ sprintf(sec,"0%d",seconds); }else{ sprintf(sec,"%d",seconds); } sprintf(t,"%s:%s:%s:%s",dd, hh, mi, sec); } //------------------------------------------------- Thanks in advance, Robert ..!! ro***********@si.t-com.hr Nov 15 '05 #1
5 Replies

 P: n/a "Robert Bralic" wrote in message news:dg**********@ss405.t-com.hr... I weated a simple program, he is compiled with gcc, and generates prim numbers, with fastes method that I find.He is based on divide with generated prim numbers... At end he gives time report on format: dd:hh:mi:sec... Precompile as gcc prim.c -o prim, and use him as "prim upper_bound",as example: "prim 1000".If anybody have some idea how to make algorithm fastes write to me...!! Prime number generation is off-topic in this group. Try mathematical groups. Alex Nov 15 '05 #2

 P: n/a In article , Robert Bralic wrote:I weated a simple program, he is compiledwith gcc, and generates prim numbers,with fastes method that I find.He is basedon divide with generated prim numbers... Well, once you've generated "2", there's not much point in incrementing the candidate by 1 each time... -- These .signatures are sold by volume, and not by weight. Nov 15 '05 #3

 P: n/a Robert Bralic wrote: Dear, I weated a simple program, he is compiled with gcc, and generates prim numbers, with fastes method that I find.He is based on divide with generated prim numbers... At end he gives time report on format: dd:hh:mi:sec... Precompile as gcc prim.c -o prim, and use him as "prim upper_bound",as example: "prim 1000".If anybody have some idea how to make algorithm fastes write to me...!! [snip] /* * All the primes less than 2^32 */ #include #define MAX_PRIMES 6542 #define K_MAX 715827882 unsigned long primes[MAX_PRIMES], pcount, tpcount ; unsigned long isqrt(unsigned long x) { unsigned long i = 0, b=1<<15 ; do { i^=b; if( i*i > x ) i^=b; } while(b>>=1); return i ; } int isp(unsigned long x) { unsigned long i, r ; r = isqrt(x) ; for ( i = 1 ; i < MAX_PRIMES ; i++ ) { if ( primes[i] > r ) break ; if ( x % primes[i] == 0 ) return 0 ; } if ( pcount < MAX_PRIMES ) { primes[pcount++] = x ; } tpcount++ ; if ( tpcount % 100000 == 0 ) printf("%ld %ld\n",x,tpcount) ; return 1 ; } int main(int argc, char *argv[]) { unsigned long k ; primes[0] = 2 ; primes[1] = 3 ; for( k = 1, pcount = tpcount = 2 ; k < K_MAX ; k++ ) { isp(6*k-1) ; isp(6*k+1) ; } printf("%ld\n", tpcount) ; return 0 ; } Nov 15 '05 #4

 P: n/a Robert Bralic wrote: I weated a simple program, he is compiled with gcc, and generates prim numbers, with fastes method that I find.He is based on divide with generated prim numbers... At end he gives time report on format: dd:hh:mi:sec... Precompile as gcc prim.c -o prim, and use him as "prim upper_bound",as example: "prim 1000".If anybody have some idea how to make algorithm fastes write to me...!! The faster algorithm for this would be a sieve. Use a bit-field to remember which numbers have been eliminted. For each prime, eliminate all of the multiples of that prime. Then search to find the next number which has not been eliminated. That is the next prime. Repeat the process until you are done. It will be orders of magnitude faster than trial division for large values of n. Don Nov 15 '05 #5

 P: n/a In article <11**********************@f14g2000cwb.googlegroups .com>, Don wrote: Robert Bralic wrote: I weated a simple program, he is compiled with gcc, and generates prim numbers, with fastes method that I find. The faster algorithm for this would be a sieve. Use a bit-field toremember which numbers have been eliminted. For each prime, eliminateall of the multiples of that prime. That's not the *fastest* algorithm, as Robert requested. See for example, "Efficient Generation of Prime Numbers" (Joye / Paillier / Vaudenay) "Fast generation of prime numbers and secure public-key cryptographic parameters" (Maurer) or, like one the other posters said, look in one of the mathematics newsgroups. -- I was very young in those days, but I was also rather dim. -- Christopher Priest Nov 15 '05 #6

### This discussion thread is closed

Replies have been disabled for this discussion.