Flash Website Builder- Trendy Site Builder is a Flash Site Building tool that helps users build stunning websites. Check Out Custom Custom Logo Design by LogoBee. Website Design and Free Logo Templates available.
 CodingForums.com Finding prime numbers code issue

Before you post, read our: Rules & Posting Guidelines

Enjoy an ad free experience by logging in. Not a member yet? Register.
 06-27-2013, 07:48 PM PM User | #16 Old Pedant Supreme Master coder!     Join Date: Feb 2009 Posts: 24,941 Thanks: 75 Thanked 4,306 Times in 4,273 Posts Here's (nearly) the best I can do with the Sieve of Erastothenes: Code: `````` Improvements: (a) no need to initialize the array (b) only checks odd numbers (c) only marks odd increments of a found prime (d) doesn't bother marking a found prime The next step: Would only save memory, not speed. And probably not even that with JavaScript coding. Have each element of the array represent an ODD number. That is, the element numbering doesn't match the numbers represented. So the array can be half the size it is now. Aside from changing algorithms, do you see a way to improve that? __________________ An optimist sees the glass as half full. A pessimist sees the glass as half empty. A realist drinks it no matter how much there is.
 06-27-2013, 07:50 PM PM User | #17 DrDOS Senior Coder   Join Date: Sep 2010 Posts: 1,878 Thanks: 15 Thanked 224 Times in 224 Posts Let's say that you want to check the first million primes, notice that I've conveniently chosen a limit that is the square of another number, and that number is composite ! Then you only need to check against primes that are less than 1,000. Make your life simpler by setting reasonable conditions. __________________ Welcome to http://www.myphotowizard.net where you can edit images, make a photo calendar, add text to images, and do much more. When you know what you're doing it's called Engineering, when you don't know, it's called Research and Development. And you can always charge more for Research and Development.
 06-27-2013, 08:00 PM PM User | #18 Old Pedant Supreme Master coder!     Join Date: Feb 2009 Posts: 24,941 Thanks: 75 Thanked 4,306 Times in 4,273 Posts DrDos: Ummm...no. (a) The first million *PRIMES* will not be found in the first million numbers. Not even close. I think you mean "all prime numbers that are less than one million". (b) If that's a comment on my Sieve of Erastothenes implementation, I still don't see it. With the Sieve, any non-marked number is prime. So if I don't continue the INNER loop all the way to MAXNUM, I won't be marking all non-primes. And if I don't continue the outer loop all the way to MAXNUM, I won't *find* all the non-marked numbers so won't find all the primes. __________________ An optimist sees the glass as half full. A pessimist sees the glass as half empty. A realist drinks it no matter how much there is.
06-27-2013, 08:03 PM   PM User | #19
DrDOS
Senior Coder

Join Date: Sep 2010
Posts: 1,878
Thanks: 15
Thanked 224 Times in 224 Posts
Quote:
 Originally Posted by Old Pedant DrDos: Ummm...no. (a) The first million *PRIMES* will not be found in the first million numbers. Not even close. I think you mean "all prime numbers that are less than one million". (b) If that's a comment on my Sieve of Erastothenes implementation, I still don't see it. With the Sieve, any non-marked number is prime. So if I don't continue the INNER loop all the way to MAXNUM, I won't be marking all non-primes. And if I don't continue the outer loop all the way to MAXNUM, I won't *find* all the non-marked numbers so won't find all the primes.
You're right sir! I really meant the primes in the first million numbers, not the first million primes.
__________________
Welcome to http://www.myphotowizard.net

where you can edit images, make a photo calendar, add text to images, and do much more.

When you know what you're doing it's called Engineering, when you don't know, it's called Research and Development. And you can always charge more for Research and Development.

 06-27-2013, 08:06 PM PM User | #20 Old Pedant Supreme Master coder!     Join Date: Feb 2009 Posts: 24,941 Thanks: 75 Thanked 4,306 Times in 4,273 Posts Okay, I do see that the marking and checking can be done separately, and then the marking only has to go to the square root of the max: Code: `````` All that really saves is the time for the inner for loop to discover that it won't run at all once chk is past the square root of max. At the expense of having to run another loop to collect the primes. I'd guess that's close to a wash. __________________ An optimist sees the glass as half full. A pessimist sees the glass as half empty. A realist drinks it no matter how much there is.
06-27-2013, 08:45 PM   PM User | #21
Regular Coder

Join Date: Jan 2013
Location: Germany
Posts: 578
Thanks: 4
Thanked 77 Times in 77 Posts
Quote:
 Originally Posted by Old Pedant Okay, I give up. How does using the square root of the number being checked apply to the Sieve of Erastothenes algorithm???
Yeah, you're right – I mixed some things up there (namely the sieve and a prime number check). My mistake.

 06-28-2013, 06:52 PM PM User | #22 007julien Regular Coder   Join Date: May 2012 Location: France Posts: 174 Thanks: 0 Thanked 27 Times in 25 Posts A simple page for prime numbers which use the preceding primes to test a new number. And a more subtle function (from rnd.me ? I can not find the post) that stores the previous calculations to go faster Code: `````` After 9 you have only to check 5+6*k and 5+6*k+2 (the other are even or divisible by 3) Strange prime numbers : 11113, 11117, 11119, 22229, 33331, 44449, 77773, 88883, 99991 ... Last edited by 007julien; 06-28-2013 at 11:36 PM..
 06-28-2013, 06:59 PM PM User | #23 Philip M Supreme Master coder!     Join Date: Jun 2002 Location: London, England Posts: 17,472 Thanks: 200 Thanked 2,469 Times in 2,447 Posts Code: ```Is this number prime? ``` __________________ All the code given in this post has been tested and is intended to address the question asked. Unless stated otherwise it is not just a demonstration.

 Bookmarks

 Tags numbers, prime, prime numbers

 Thread Tools Rate This Thread Rate This Thread: 5 : Excellent 4 : Good 3 : Average 2 : Bad 1 : Terrible

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is Off Forum Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home :: Client side development     JavaScript programming         DOM and JSON scripting         Ajax and Design         JavaScript frameworks         Post a JavaScript     HTML & CSS     XML     Flash & ActionScript         Adobe Flex     Graphics and Multimedia discussions     General web building         Site reviews         Building for mobile devices :: Server side development     Apache configuration     Perl/ CGI     PHP         Post a PHP snippet     MySQL         Other Databases     Ruby & Ruby On Rails     ASP     ASP.NET     Java and JSP     Other server side languages/ issues         ColdFusion         Python :: Computing & Sciences     Computer Programming     Computer/PC discussions     Geek News and Humour Web Projects and Services Marketplace     Web Projects         Small projects (quick fixes and changes)         Medium projects (new script, new features, etc)         Large Projects (new web application, complex features etc)         Unknown sized projects (request quote)         Vacant job positions         Looking for work/ for hire         Project collaboration/ partnership         Paid work offers and requests (Now CLOSED)     Career, job, and business ideas or advice     Domains, Sites, and Designs for sale         Domains for sale         Websites for sale         Design templates and graphics for sale :: Other forums     Member Offers     Forum feedback and announcements

All times are GMT +1. The time now is 06:03 PM.