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

Discussion in 'C Programming' started by Robert Bralic, Sep 21, 2005.

1. ### Robert BralicGuest

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

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

-com.hr

Robert Bralic, Sep 21, 2005

2. ### Alexei A. FrounzeGuest

"Robert Bralic" <> wrote in message
news:dgqri9\$n81\$-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

Alexei A. Frounze, Sep 21, 2005

3. ### Walter RobersonGuest

In article <dgqri9\$n81\$-com.hr>,
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...

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.

Walter Roberson, Sep 21, 2005
4. ### BerryoGuest

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

Berryo, Sep 21, 2005
5. ### DonGuest

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

Don, Oct 13, 2005
6. ### Walter RobersonGuest

In article <>,
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 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

Walter Roberson, Oct 13, 2005