Loading ...
Sorry, an error occurred while loading the content.

Re: [PrimeNumbers] SEARCHING FOR A GOOD ALTERNATIVE

Expand Messages
  • Ben Bradley
    ... Oh good, a question that doesn t involve elliptical curves. :) I hope I can adequately answer it. The sequence of odd numbers does not contain all primes.
    Message 1 of 5 , Mar 10 7:36 AM
    • 0 Attachment
      At 06:06 AM 3/10/04 -0800, H.BARGHOUT wrote:
      >Hi all
      >i would like to ask if any body has a way to generate
      >a sequence of numbers that containes all prime, faster
      >than generating all odd number

      Oh good, a question that doesn't involve elliptical curves. :) I hope I
      can adequately answer it.

      The sequence of odd numbers does not contain all primes. There's one
      prime not included, the even number 2. I know that's just a detail, but
      mathematics people are sticklers for detail. :)

      There's the 'wheel' which is a method for efficiently storing
      consecutive primes, that I think might be what you're looking for. Here's
      an earlier message about it (I've posted this link before, I think it's
      really neat):
      http://groups.yahoo.com/group/primenumbers/message/10491

      This misses the earliest primes in the first 'rotation' of the wheel,
      but as that message says, you already 'know' that they are prime. Rotating
      this 'wheel' may or may not be faster than incrementing an odd number by 2
      (going through all the odd numbers), depending on implementation. Actually,
      going through the odd numbers is effectively using a wheel of length 2. A
      wheel of any size appears to be linear processes (increasing the range of
      numbers they go over increases the time it takes in direct proportion), so
      in the realm of algorithms, these both take the same amount of time.

      >thank you in advance

      ---
      http://mindspring.com/~benbradley
    • Hadley, Thomas H (Tom), ALABS
      ... From: H.BARGHOUT [mailto:hamedbar@yahoo.com] Sent: Wednesday, March 10, 2004 8:07 AM To: primenumbers@yahoogroups.com Subject: [PrimeNumbers] SEARCHING FOR
      Message 2 of 5 , Mar 10 7:57 AM
      • 0 Attachment
        -----Original Message-----
        From: H.BARGHOUT [mailto:hamedbar@...]
        Sent: Wednesday, March 10, 2004 8:07 AM
        To: primenumbers@yahoogroups.com
        Subject: [PrimeNumbers] SEARCHING FOR A GOOD ALTERNATIVE


        Hi all
        i would like to ask if any body has a way to generate
        a sequence of numbers that containes all prime, faster
        than generating all odd number
        thank you in advance

        -----End Original Message-----
        Here are two algorithms to generate a sequence of numbers
        that contains all the primes. (both are wheel generators)

        print 2
        print 3
        n=5
        for( ever )
        print n
        n = n+2
        print n
        n = n+4
        end for

        Or with a bigger wheel:
        print 2
        print 3
        print 5
        n=7
        for( ever )
        print n
        n = n+4
        print n
        n = n+2
        print n
        n = n+4
        print n
        n = n+2
        print n
        n = n+4
        print n
        n = n+6
        print n
        n = n+2
        print n
        n = n+6
        end for
      • Dan Morenus
        I suppose it s worth asking whether the original poster wanted a sequence that contained all the prime numbers, or a sequence that consisted entirely of prime
        Message 3 of 5 , Mar 10 9:03 AM
        • 0 Attachment
          I suppose it's worth asking whether the original poster wanted a sequence that
          contained all the prime numbers, or a sequence that consisted entirely of prime
          numbers but doesn't necessarily contain all of them.

          "Hadley, Thomas H (Tom), ALABS" wrote:
          >
          > -----Original Message-----
          > From: H.BARGHOUT [mailto:hamedbar@...]
          > Sent: Wednesday, March 10, 2004 8:07 AM
          > To: primenumbers@yahoogroups.com
          > Subject: [PrimeNumbers] SEARCHING FOR A GOOD ALTERNATIVE
          >
          > Hi all
          > i would like to ask if any body has a way to generate
          > a sequence of numbers that containes all prime, faster
          > than generating all odd number
          > thank you in advance
          >
          > -----End Original Message-----
          > Here are two algorithms to generate a sequence of numbers
          > that contains all the primes. (both are wheel generators)
          >
          > print 2
          > print 3
          > n=5
          > for( ever )
          > print n
          > n = n+2
          > print n
          > n = n+4
          > end for
          >
          > Or with a bigger wheel:
          > print 2
          > print 3
          > print 5
          > n=7
          > for( ever )
          > print n
          > n = n+4
          > print n
          > n = n+2
          > print n
          > n = n+4
          > print n
          > n = n+2
          > print n
          > n = n+4
          > print n
          > n = n+6
          > print n
          > n = n+2
          > print n
          > n = n+6
          > end for
          >
          > Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
          > The Prime Pages : http://www.primepages.org/
          >
          >
          > Yahoo! Groups Links
          >
          >
          >
          >

          -- Dan Morenus (dmorenus@...)

          -- This parachute is not warranted to be suitable --
          -- for any purpose, including descending safely --
          -- from an airplane to the ground. --
        • Jens Kruse Andersen
          ... [snipped] (Just having fun) Below is a slightly obfuscated C wheel generator generator (no stuttering) . Set m = largest prime used in the wheel. The
          Message 4 of 5 , Mar 10 11:11 AM
          • 0 Attachment
            Thomas H Hadley wrote:
            > From: H.BARGHOUT [mailto:hamedbar@...]
            > i would like to ask if any body has a way to generate
            > a sequence of numbers that containes all prime, faster
            > than generating all odd number
            > thank you in advance
            >
            > -----End Original Message-----
            > Here are two algorithms to generate a sequence of numbers
            > that contains all the primes. (both are wheel generators)
            [snipped]

            (Just having fun)
            Below is a slightly obfuscated C wheel generator generator (no stuttering) .
            Set m = largest prime used in the wheel.
            The output is a C wheel generator.
            m=3 and m=5 gives Hadley's two algorithms.

            #include <stdio.h>
            unsigned m=7,p,oldp=1,d,n,primor=1;
            unsigned pn[1000];
            main(void) {
            printf("#include <stdio.h>\nunsigned n=1;\nmain(void){\n");
            for (p=2;p<=m;p++) { /*print primes<=m*/
            for (d=2;p%d;d++) ;
            if (d==p) {
            printf("printf(\"%u\\n\");\n",p);
            pn[n++]=p;
            primor*=p;
            }
            }
            printf("for(;;) {\n");
            for(p=m;p<=primor+m;p++) {
            for(d=0;(d<n)&&(p%pn[d]);d++) ;
            if (d==n) {
            printf("n+=%2u; ",p-oldp);
            printf("printf(\"%%u\\n\",n);\n",p);
            oldp=p;
            }
            }
            printf("}\nreturn 0;\n}\n");
            return 0;
            }

            Here is the output for m=7, skipping numbers divisible by 2,3,5,7:

            #include <stdio.h>
            unsigned n=1;
            main(void){
            printf("2\n");
            printf("3\n");
            printf("5\n");
            printf("7\n");
            for(;;) {
            n+=10; printf("%u\n",n);
            n+= 2; printf("%u\n",n);
            n+= 4; printf("%u\n",n);
            n+= 2; printf("%u\n",n);
            n+= 4; printf("%u\n",n);
            n+= 6; printf("%u\n",n);
            n+= 2; printf("%u\n",n);
            n+= 6; printf("%u\n",n);
            n+= 4; printf("%u\n",n);
            n+= 2; printf("%u\n",n);
            n+= 4; printf("%u\n",n);
            n+= 6; printf("%u\n",n);
            n+= 6; printf("%u\n",n);
            n+= 2; printf("%u\n",n);
            n+= 6; printf("%u\n",n);
            n+= 4; printf("%u\n",n);
            n+= 2; printf("%u\n",n);
            n+= 6; printf("%u\n",n);
            n+= 4; printf("%u\n",n);
            n+= 6; printf("%u\n",n);
            n+= 8; printf("%u\n",n);
            n+= 4; printf("%u\n",n);
            n+= 2; printf("%u\n",n);
            n+= 4; printf("%u\n",n);
            n+= 2; printf("%u\n",n);
            n+= 4; printf("%u\n",n);
            n+= 8; printf("%u\n",n);
            n+= 6; printf("%u\n",n);
            n+= 4; printf("%u\n",n);
            n+= 6; printf("%u\n",n);
            n+= 2; printf("%u\n",n);
            n+= 4; printf("%u\n",n);
            n+= 6; printf("%u\n",n);
            n+= 2; printf("%u\n",n);
            n+= 6; printf("%u\n",n);
            n+= 6; printf("%u\n",n);
            n+= 4; printf("%u\n",n);
            n+= 2; printf("%u\n",n);
            n+= 4; printf("%u\n",n);
            n+= 6; printf("%u\n",n);
            n+= 2; printf("%u\n",n);
            n+= 6; printf("%u\n",n);
            n+= 4; printf("%u\n",n);
            n+= 2; printf("%u\n",n);
            n+= 4; printf("%u\n",n);
            n+= 2; printf("%u\n",n);
            n+=10; printf("%u\n",n);
            n+= 2; printf("%u\n",n);
            }
            return 0;
            }

            It has been tested and works.
            The optimal m is machine and application dependent.
            Printing takes far longer than adding in practice.
            Besides, I suspect the original poster did not know what he really needed.
            If the generated numbers are used for something where only primes were really
            necessary, then only generating the primes with the sieve of Eratosthenes would
            probably be much faster.

            --
            Jens Kruse Andersen
          Your message has been successfully submitted and would be delivered to recipients shortly.