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

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

  1. 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 ..!!
    -com.hr
     
    Robert Bralic, Sep 21, 2005
    #1
    1. Advertising

  2. "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
    #2
    1. Advertising

  3. 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
    #3
  4. Robert Bralic

    Berryo Guest

    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
    #4
  5. Robert Bralic

    Don Guest

    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
    #5
  6. 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
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Ahmed Moustafa
    Replies:
    0
    Views:
    817
    Ahmed Moustafa
    Nov 15, 2003
  2. Bapaiah Katepalli
    Replies:
    1
    Views:
    1,532
    Mike Treseler
    Jun 23, 2006
  3. Jack Middleton

    Faster matrix permutation algorithm?

    Jack Middleton, Aug 13, 2005, in forum: C Programming
    Replies:
    3
    Views:
    785
    russell kym horsell
    Aug 14, 2005
  4. Jack

    Questions on Prim's algorithm

    Jack, Apr 15, 2006, in forum: C Programming
    Replies:
    1
    Views:
    851
    Keith Thompson
    Apr 15, 2006
  5. RJB
    Replies:
    23
    Views:
    1,176
    Raymond Hettinger
    May 25, 2011
Loading...

Share This Page