Erastho

[JohnFullspeed]

To work on PN(Primes Number) the first thing is to have le primes list
Eratosthenes sieve is The solution

We fifind nf any where the logc (Wiky ,MartWord...)
Before to see if my results can be interested I try to have performances of the classic sieves

Asking at one author i have this remark: my version have 3200 lines.
Mine only 20. The question is what I forget.
What xxx does in the 3180 other lines.
XXX is a senior programmer of this forum not a beginner.

I compute with my Eratosthenes ALL the primes less <32 bits 210 000 000
I control them with the division method: Of course they are all prime

Remark;

On the Forum sometimes QS is use for Quadratic Sieve It's wrong QS means Quick Sort. So I link for exemple to Jasonp makiing the mistake: I don't understand where a QS is use in a quadrartic sieve,
Like we say in Frarnce on appelle chat un chat pas chien

John

[ET_]

Let's call the A.A.A.A.

Association Against Acronym Abuse.

Luigi

[science_man_88]

Originally Posted by JohnFullspeed

To work on PN(Primes Number) the first thing is to have le primes list
Eratosthenes sieve is The solution

We fifind nf any where the logc (Wiky ,MartWord...)
Before to see if my results can be interested I try to have performances of the classic sieves

Asking at one author i have this remark: my version have 3200 lines.
Mine only 20. The question is what I forget.
What xxx does in the 3180 other lines.
XXX is a senior programmer of this forum not a beginner.

I compute with my Eratosthenes ALL the primes less <32 bits 210 000 000
I control them with the division method: Of course they are all prime

Remark;

On the Forum sometimes QS is use for Quadratic Sieve It's wrong QS means Quick Sort. So I link for exemple to Jasonp makiing the mistake: I don't understand where a QS is use in a quadrartic sieve,
Like we say in Frarnce on appelle chat un chat pas chien

John

To work on PN(Primes Number) the first thing is to have le primes list
Eratosthenes sieve is The solution

We fifind nf any where the logc (Wiky ,MartWord...)
Before to see if my results can be interested I try to have performances of the classic sieves

Asking at one author i have this remark: my version have 3200 lines.
Mine only 20. The question is what I forget.
What xxx does in the 3180 other lines.
XXX is a senior programmer of this forum not a beginner.

I compute with my Eratosthenes ALL the primes less <32 bits 210 000 000
I control them with the division method: Of course they are all prime

Remark;

On the Forum sometimes QS is use for Quadratic Sieve It's wrong QS means Quick Sort. So I link for exemple to Jasonp makiing the mistake: I don't understand where a QS is use in a quadrartic sieve,
Like we say in Frarnce on appelle chat un chat pas chien

these are your errors in spelling ( bold ) and grammar(underline). Also, if you write better in french I have no problem dealing with you in that language I have ways of translating it.

[bsquared]

Originally Posted by JohnFullspeed

I compute with my Eratosthenes ALL the primes less <32 bits 210 000 000
I control them with the division method: Of course they are all prime

There are 203,280,221 primes less than 2^32.

And if the goal is to produce the shortest program to compute them, then 20 lines is doing ok. In 10 min of work I came up with a 16 liner, and a more motivated person could probably halve that.

int main(int argc, char **argv) {
 unsigned char *list;
 unsigned int i, j, p, c = 1, limit = strtoul(argv[1],NULL,10);
 list = (unsigned char *)calloc(limit/2, sizeof(unsigned char));
 printf("prime 0 = 2\n");
 for (i = 1; i < sqrt((double)(limit/2)); i++) {
    p = 2 * i + 1; 
    if (list[i] == 0) {
       printf("prime %d = %u\n",c++,p);
       for (j = i+p; j < limit/2; j+=p) list[j] = 1;
    }
 }
 for (; i < limit/2; i++) if (list[i] == 0) printf("prime %d = %u\n",c++,2 * i + 1);
 printf("found %d primes\n",c);
 free(list);
}

Unfortunately, it takes 75 seconds to compute all primes less than 2^32. To go faster would require more code.

[bsquared]

While waiting for Real Work to compile, I played a bit more.

The following is both faster and almost half the lines of the previous attempt. Note there is only one ';' per line (not counting the for loop header stuff).

int main(int argc, char **argv) {
 unsigned int i, j, p, c = 1, *list, limit = strtoul(argv[1],NULL,10);
 list = (unsigned int *)calloc(limit/16, sizeof(unsigned int));
 printf("prime 0 = 2\n");
 for (i = 1; i < sqrt((double)(limit/2)); i++) if ((list[i>>5] & (1 << (i & 31))) == 0) for (j = i+(2 * i + 1); j < limit/2; j+=(2 * i + 1)) list[j>>5] |= (1 << (j & 31));
 for (i = 1; i < limit/2; i++) if ((list[i>>5] & (1 << (i & 31))) == 0) printf("prime %d = %u\n",c++,2 * i + 1);
 printf("found %d primes\n",c);
 free(list);
}

[science_man_88]

Originally Posted by bsquared

While waiting for Real Work to compile, I played a bit more.

The following is both faster and almost half the lines of the previous attempt. Note there is only one ';' per line (not counting the for loop header stuff).

int main(int argc, char **argv) {
 unsigned int i, j, p, c = 1, *list, limit = strtoul(argv[1],NULL,10);
 list = (unsigned int *)calloc(limit/16, sizeof(unsigned int));
 printf("prime 0 = 2\n");
 for (i = 1; i < sqrt((double)(limit/2)); i++) if ((list[i>>5] & (1 << (i & 31))) == 0) for (j = i+(2 * i + 1); j < limit/2; j+=(2 * i + 1)) list[j>>5] |= (1 << (j & 31));
 for (i = 1; i < limit/2; i++) if ((list[i>>5] & (1 << (i & 31))) == 0) printf("prime %d = %u\n",c++,2 * i + 1);
 printf("found %d primes\n",c);
 free(list);
}

in PARI ( john it's a math console) I can get it to :

a=vector(<number to check up to>,n,if(isprime(n),n,0));a=vecsort(a,,8);a=vector(#a-1,n,a[n+1]);a

[science_man_88]

Originally Posted by science_man_88

in PARI ( john it's a math console) I can get it to :

a=vector(<number to check up to>,n,if(isprime(n),n,0));a=vecsort(a,,8);a=vector(#a-1,n,a[n+1]);a

okay yeah I forgot vectors can only be so long, dang.

[Christenson]

Originally Posted by ET_

Let's call the A.A.A.A.

Association Against Acronym Abuse.

Luigi

Sorry, that's not a TLA, I don't understand!

[Christenson]

Originally Posted by JohnFullspeed

Asking at one author i have this remark: my version have 3200 lines.
Mine only 20. The question is what I forget.
What xxx does in the 3180 other lines.
XXX is a senior programmer of this forum not a beginner.

John

As you see above, there are distinct tradeoffs between size of program and its speed, and different ways of counting lines. I can tell you that using GWNUM (from Prime95) will definitely increase the size of a program, but it will allow it to work with really large numbers.

Your author may have been liberal with the use of whitespace in his program, too. Maybe you should ask him/her for source code?

As SM88 suggested, it is probably better for you to write in French first, then post the translation below.

[jasonp]

Originally Posted by JohnFullspeed

On the Forum sometimes QS is use for Quadratic Sieve It's wrong QS means Quick Sort. So I link for exemple to Jasonp makiing the mistake: I don't understand where a QS is use in a quadrartic sieve,

So the universe only has 26*26=676 things whose name has two words?

(Google queries with 'nfs' get huge numbers of hits for a game called 'need for speed' :)

[science_man_88]

Originally Posted by Christenson

As you see above, there are distinct tradeoffs between size of program and its speed, and different ways of counting lines. I can tell you that using GWNUM (from Prime95) will definitely increase the size of a program, but it will allow it to work with really large numbers.

Your author may have been liberal with the use of whitespace in his program, too. Maybe you should ask him/her for source code?

As SM88 suggested, it is probably better for you to write in French first, then post the translation below.

they told me in a french PM that from what I can make out enough to get a rough translation says they have Alzheimer's or Parkinson's .