Chat LIVE With Programming Experts! There Are 23 Online Right Now...

Programming Help

Web Development



What's Here?

  • Members: 244,203
  • Replies: 692,949
  • Topics: 113,132
  • Snippets: 3,863
  • Tutorials: 935
  • Total Online: 1,453
  • Members: 88
  • Guests: 1,365
 

Code Snippets

  

PHP Source Code
Welcome to Dream.In.Code
Become a PHP Expert!

Join 244,203 PHP Programmers for FREE! Get instant access to thousands of PHP experts, tutorials, code snippets, and more! There are 1,453 people online right now. Registration is fast and FREE... Join Now!





Sieve of Eratosthenes

Implementation of the Sieve of Eratosthenes algorithm for finding prime numbers from 2 to N.

Submitted By: grimpirate
Actions:
Rating:
Views: 386

Language: PHP
Last Modified: August 20, 2008
Instructions: The function takes as input the limit to which you wish to determine prime numbers (only tested up to 200,000 effectively as largest integer at 600,000 the computer hung).

Snippet


  1. function sieve_of_eratosthenes($limit){
  2.         if(!is_int($limit)) return false;
  3.         if($limit < 1) return false;
  4.         $primes = array(1);
  5.         if($limit == 1) return $primes;
  6.         $numbers = array_fill(2, $limit - 1, null);
  7.         do{
  8.                 $start = reset($numbers);
  9.                 $start = key($numbers);
  10.                 $end = end($numbers);
  11.                 $end = key($numbers);
  12.                 unset($numbers[$start]);
  13.                 $primes[] = $start;
  14.                 $inc = $start;
  15.                 $start = bcmul($start, $start);
  16.                 for($i = $start; bccomp($i, $end) <= 0; $i = bcadd($i, $inc))
  17.                         unset($numbers[$i]);
  18.         }while(bccomp($start, $limit) < 0);
  19.         return array_merge($primes, array_keys($numbers));
  20. }

Copy & Paste

Comments


There are currently no comments for this snippet. Be the first to comment!

Add comment


You must be registered and logged on to </dream.in.code> to leave comments.





Live PHP Help!

Be Social

Dream.In.Code RSS Feed Dream.In.Code LinkedIn Group Follow Us On Twitter Fan Us On Facebook

PHP Tutorials

Reference Sheets

PHP Snippets

DIC Chatroom

Bye Bye Ads

Monthly Drawing

Thumb Drive

Top Contributors

Top 10 Kudos This Month