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

Re: [PrimeNumbers] SEARCHING FOR A GOOD ALTERNATIVE

Expand Messages
  • 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 1 of 5 , Mar 10, 2004
    • 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.