By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
426,012 Members | 988 Online
Bytes IT Community
+ Ask a Question
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<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 ..!!
ro***********@si.t-com.hr
Nov 15 '05 #1
Share this Question
Share on Google+
5 Replies


P: n/a
"Robert Bralic" <ro*********@yahoo.co.uk> 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 <dg**********@ss405.t-com.hr>,
Robert Bralic <ro*********@yahoo.co.uk> 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.
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 <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 ;
}

Nov 15 '05 #4

P: n/a
Don

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 <do*******@gmail.com> 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
Nov 15 '05 #6

This discussion thread is closed

Replies have been disabled for this discussion.