Velocity Reviews > Faster algorithm for prim numbers in C...???

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

Robert Bralic
Guest
Posts: n/a

 09-21-2005
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;
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);
}

//-------------------------------------------------

http://www.velocityreviews.com/forums/(E-Mail Removed)-com.hr

Alexei A. Frounze
Guest
Posts: n/a

 09-21-2005
"Robert Bralic" <(E-Mail Removed)> wrote in message
news:dgqri9\$n81\$(E-Mail Removed)-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

Walter Roberson
Guest
Posts: n/a

 09-21-2005
In article <dgqri9\$n81\$(E-Mail Removed)-com.hr>,
Robert Bralic <(E-Mail Removed)> 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...

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.

Berryo
Guest
Posts: n/a

 09-21-2005

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 <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[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 ;
}

Don
Guest
Posts: n/a

 10-13-2005

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

Walter Roberson
Guest
Posts: n/a

 10-13-2005
In article <(E-Mail Removed) .com>,
Don <(E-Mail Removed)> 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 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.
--
I was very young in those days, but I was also rather dim.
-- Christopher Priest