fonction isprime et crible d'ératosthène

[Adriweb]

can't you just reserve a bigger list first so that it doesn't need to grow?

[parisse]

Thanks, good answer, I remember that I tried with C and ndless, but it was a really headache (I feel more comfortable with C++ and STL), so maybe my implementation was not efficient.

C++ and STL are supported by ndless today.

For 20000, sieve runs in around 5 seconds and naive runs in 1.4 second

20000 is really small, trial division will need at most 34 divisions to check primality (and most of the time 5 divisions will return false). FYI, with KhiCAS, ithprime(1000000) returns 15485863 in a few seconds on a CX/CXII, it does a sieve with about 1000 times more entries than yours to find the 1000000th prime.

You can't deduce much comparing algorithms with TI Basic because it's interpreted and therefore n will be small. And trying to optimize with an interpreted language will not help much, in fact I would not recommend to do that if you want to really optimize, therefore with a compiled language, because the good pratices are sometimes opposite.

[Heneos]

C++ and STL are supported by ndless today.

Could you give me a link or tutorial about C ++ in ndless?

20000 is really small, trial division will need at most 34 divisions to check primality (and most of the time 5 divisions will return false). FYI, with KhiCAS, ithprime(1000000) returns 15485863 in a few seconds on a CX/CXII, it does a sieve with about 1000 times more entries than yours to find the 1000000th prime.

Well, this is because Sieve has a bigger complexity than primality test. But for listing primes in a range, sieve is an efficient method. You can realize this if you use:

Code: Tout sélectionner

for(int i=1; i<n; i++){
if(isPrime(i)) printf("%d is prime",i);
}

the time complexity is

$mathjax$O(n\times \mathrm{isPrime()})$mathjax$

.
But in Sieve the complexity is

$mathjax$O(n\log(\log(n)))$mathjax$

.
Miller-Rabin primality test has a complexity around

$mathjax$O(\log(n)^{3})$mathjax$

.
So isPrime is more efficient than Miller-Rabin, but as you said, it is because it is interpreted.

[Heneos]

with KhiCAS, ithprime(1000000) returns 15485863 in a few seconds on a CX/CXII, it does a sieve with about 1000 times more entries than yours to find the 1000000th prime.

Meissel-Lehmer algorithm provides a more efficient way to determine the ith prime number, but it's quite different than Sieve or Primality Test.

[parisse]

C++ and STL are supported by ndless today.

Could you give me a link or tutorial about C ++ in ndless?

Do the same as for a C program, but run nspire-g++ instead of nspire-gcc.

So isPrime is more efficient than Miller-Rabin, but as you said, it is because it is interpreted.

Maybe you are calling Miller-Rabin without doing trial division first. And otherwise, trial division code is way faster compiled versus interpreted.

[parisse]

Meissel-Lehmer algorithm provides a more efficient way to determine the ith prime number, but it's quite different than Sieve or Primality Test.

Like trial division vs Miller-Rabin, sieving *is* efficient for finding the ith prime for not too large values of n (remember we are on a calculator...).