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

[Robert Bralic]

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<stdio.h>
#include<malloc.h>
#include<time.h>

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;i<k;i++){
exit:
tekuci_drugi=prvi;
while(tekuci_drugi->next){
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 ..!!
(e-mail address removed)-com.hr

 

[Alexei A. Frounze]

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

 

[Walter Roberson]

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...

Well, once you've generated "2", there's not much point in incrementing
the candidate by 1 each time...

 

[Berryo]

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 <stdio.h>

#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 > r ) break ;
if ( x % primes == 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 ;
}

 

[Don]

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

 

[Walter Roberson]

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.

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.