Programming Help

Web Development



What's Here?

  • Members: 149,626
  • Replies: 506,753
  • Topics: 79,851
  • Snippets: 2,666
  • Tutorials: 706
  • Total Online: 1,985
  • Members: 76
  • Guests: 1,909
 

Code Snippets

  

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

Join 149,626 PHP Programmers for FREE! Get instant access to thousands of PHP experts, tutorials, code snippets, and more! There are 1,985 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: 186

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.




Be Social

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

Live PHP Help!

PHP Tutorials

Reference Sheets

PHP Snippets

DIC Chatroom

Bye Bye Ads

Monthly Drawing

Thumb Drive

Top Contributors

Top 10 Kudos This Month