Re: Strawmans prime sieve/filter

From	"Chris M. Thomasson" <no@spam.invalid>
Newsgroups	comp.lang.javascript
Subject	Re: Strawmans prime sieve/filter
Date	2013-09-09 21:08 -0700
Organization	Aioe.org NNTP Server
Message-ID	<l0m5vq$j4m$1@speranza.aioe.org> (permalink)
References	<6e464d33-47e4-41b8-bfda-19511de92915@googlegroups.com> <l0jgv8$g2u$1@news.albasani.net> <5837258c-4fbe-4c8d-a432-b7e8e5b59495@googlegroups.com>

Show all headers | View raw

> wrote in message 
> news:5837258c-4fbe-4c8d-a432-b7e8e5b59495@googlegroups.com...

> Den måndagen den 9:e september 2013 kl. 05:57:27 UTC+2 skrev Stefan Weiss:
> > On 2013-09-09 04:09, jonas.thornvall@gmail.com wrote:
> >
> > > It writes all 1 270608 primes less then 20 000 004 into an array in
> >
> > > 17 seconds by comparing the natural with the value read into the 
> > > array, but
> >
> > > bigger then 20 million there is to many primes to compare with and it
> >
> > > gets slow. I only compare the values in prime array upto square of the
> >
> > > natural.

[...]

> I am waiting for you to post a faster sieve of the primes upto 20 
> millions.
> It is extrordinary that what you call trial division is faster the 
> Eratosthenes.

[...]

FWIW, here is stupid simple code that finds 1,270,607 prime numbers out of
20,000,000 with average time of 12,500 milliseconds on my little notebook
using Firefox:
______________________________________________________________
<!DOCTYPE html>
<html>
    <title>Primes</title>

    <script type="text/javascript">
        function is_prime(n)
        {
            if (isNaN(n) || ! isFinite(n) || n % 1 || n < 2)
                return false;

            if (! (n % 2)) return (n == 2);
            if (! (n % 3)) return (n == 3);

            var m = Math.sqrt(n);

            for (var i = 5; i <= m; i += 6)
            {
                if (! (n % i) || ! (n % (i + 2)))
                    return false;
            }

            return true;
        }


        function count_prime(m)
        {
            var c = 0;

            for (var n = 2; n < m; ++n)
                if (is_prime(n)) ++c;

            return c;
        }


        function main()
        {
            console.time("count_prime");

            var c = count_prime(20000000);

            console.timeEnd("count_prime");

            alert("Found " + c + " Primes.");
        }
    </script>

    <body onload="main();">

    </body>
</html>
______________________________________________________________


I have no idea if this is anywhere near what you are looking for Jonas...

;^o

Thread

Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-08 19:09 -0700
  Re: Strawmans prime sieve/filter Stefan Weiss <krewecherl@gmail.com> - 2013-09-09 05:57 +0200
    Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-08 21:22 -0700
    Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-08 21:50 -0700
      Re: Strawmans prime sieve/filter Stefan Weiss <krewecherl@gmail.com> - 2013-09-09 13:45 +0200
        Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-09 06:33 -0700
        Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-09 06:41 -0700
          Re: Strawmans prime sieve/filter Stefan Weiss <krewecherl@gmail.com> - 2013-09-09 18:37 +0200
          Re: Strawmans prime sieve/filter Stefan Weiss <krewecherl@gmail.com> - 2013-09-09 19:54 +0200
            Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-09 12:46 -0700
              Re: Strawmans prime sieve/filter Stefan Weiss <krewecherl@gmail.com> - 2013-09-09 23:25 +0200
                Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-09 14:58 -0700
        Re: Strawmans prime sieve/filter Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2013-09-11 10:39 +0200
          Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-11 02:54 -0700
          Re: Strawmans prime sieve/filter Stefan Weiss <krewecherl@gmail.com> - 2013-09-11 12:59 +0200
          Re: Strawmans prime sieve/filter Dr J R Stockton <reply1300@merlyn.demon.co.uk.invalid> - 2013-09-12 20:17 +0100
            Re: Strawmans prime sieve/filter Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2013-09-13 02:27 +0200
              Re: Strawmans prime sieve/filter Stefan Weiss <krewecherl@gmail.com> - 2013-09-13 04:03 +0200
                Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-12 19:30 -0700
                Re: Strawmans prime sieve/filter Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2013-09-13 05:15 +0200
                Re: Strawmans prime sieve/filter Stefan Weiss <krewecherl@gmail.com> - 2013-09-13 05:27 +0200
                Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-13 08:26 -0700
                Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-13 08:15 -0700
                Re: Strawmans prime sieve/filter Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2013-09-13 19:13 +0200
                Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-13 17:15 -0700
                Re: Strawmans prime sieve/filter Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-09-14 01:55 +0100
                Re: Strawmans prime sieve/filter Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2013-09-14 04:20 +0200
                Re: Strawmans prime sieve/filter Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-09-14 06:16 +0100
                Re: Strawmans prime sieve/filter Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2013-09-14 12:10 +0200
                Re: Strawmans prime sieve/filter Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-09-14 12:49 +0100
                Re: Strawmans prime sieve/filter Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2013-09-14 15:23 +0200
                Re: Strawmans prime sieve/filter Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-09-14 21:51 +0100
                Re: Strawmans prime sieve/filter Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2013-09-15 03:32 +0200
                Re: Strawmans prime sieve/filter Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-09-15 04:07 +0100
                Re: Strawmans prime sieve/filter Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2013-09-15 18:57 +0200
                Re: Strawmans prime sieve/filter Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-09-15 19:24 +0100
                Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-14 20:37 -0700
                Re: Strawmans prime sieve/filter Dr J R Stockton <reply1300@merlyn.demon.co.uk.invalid> - 2013-09-14 19:38 +0100
    Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-08 22:26 -0700
      Re: Strawmans prime sieve/filter Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-09-10 22:48 +0100
        Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-11 00:36 -0700
          Re: Strawmans prime sieve/filter Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-09-11 14:47 +0100
    Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-08 22:33 -0700
      Re: Strawmans prime sieve/filter "Chris M. Thomasson" <no@spam.invalid> - 2013-09-09 21:08 -0700
        Re: Strawmans prime sieve/filter "Chris M. Thomasson" <no@spam.invalid> - 2013-09-10 08:52 -0700
  Re: Strawmans prime sieve/filter Dr J R Stockton <reply1300@merlyn.demon.co.uk.invalid> - 2013-09-10 19:08 +0100
  Re: Strawmans prime sieve/filter "Chris M. Thomasson" <no@spam.invalid> - 2014-04-10 22:02 -0700
    Re: Strawmans prime sieve/filter "Chris M. Thomasson" <no@spam.invalid> - 2014-05-02 15:39 -0700
      Re: Strawmans prime sieve/filter "Chris M. Thomasson" <no@spam.invalid> - 2014-05-02 15:54 -0700

csiph-web